p226.ans1
======================
3

=================
p226.ans2
======================
-1

=================
p226.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int inf = (int)1e9;

int n, m;
vector<vector<pair<int, int>>> adj;

void read() {
    cin >> n >> m;
    adj.assign(n, {});
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--, w--;
        adj[u].push_back({v, w});
    }
}

void solve() {
    // Shortest path where consecutive edges must differ in colour, found by BFS
    // over the state (vertex, colour of the last edge used). dist[v][c] is the
    // fewest edges to reach v with the last edge coloured c. We seed all three
    // colours at the source with distance 0 so the very first edge may have any
    // colour; from state (u, w) we relax every outgoing edge (u -> v) of colour
    // w2 != w. Since all edges have weight 1, plain BFS gives the optimum, and
    // the answer is the minimum dist[n-1][c] over the three colours, or -1 if
    // the target is unreachable.

    vector<vector<int>> dist(n, vector<int>(3, inf));
    dist[0] = {0, 0, 0};

    queue<pair<int, int>> q;
    q.push({0, 0});
    q.push({0, 1});
    q.push({0, 2});

    while(!q.empty()) {
        auto [u, w] = q.front();
        q.pop();
        for(auto [v, w2]: adj[u]) {
            if(w != w2 && dist[v][w2] > dist[u][w] + 1) {
                dist[v][w2] = dist[u][w] + 1;
                q.push({v, w2});
            }
        }
    }

    int ans = min({dist[n - 1][0], dist[n - 1][1], dist[n - 1][2]});
    if(ans == inf) {
        cout << -1 << '\n';
    } else {
        cout << ans << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p226.in1
======================
4 4
1 2 1
2 3 2
3 4 3
2 4 1

=================
p226.in2
======================
3 2
1 2 1
2 3 1

=================
statement.txt
======================
226. Colored graph
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



You are given an oriented graph. Each edge of the graph is colored in one of the three colors. Your task is to find the length of the shortest path from the first vertex to the N-th. Note that any two successive edges in the path can't have the same color.

Input
The first line of the input file consists of two integers N and M (2 <= N <= 200; 0 <= M <= N*N). Next M lines contain descriptions of the edges. Each edge description is a list of three integers X, Y, C (1 <= X, Y <= N, 1 <= C <= 3), where X is the starting vertex of the edge, Y is the finishing vertex and C is the color of the edge.

Output
Output the length of the shortest path between the first and the N-th vertexes. Output "-1" if the path doesn't exist.

Sample test(s)

Input

Test #1
4 4
1 2 1
2 3 2
3 4 3
2 4 1

Test #2
3 2
1 2 1
2 3 1

Output

Test #1
3

Test #2
-1
Author:	---
Resource:	---
Date:	---







=================
