Submission #2861177

---

Source Code Expand

#include<bits/stdc++.h>
const int N = 2e5 + 5;
const int inf = 1e9 + 7;
using namespace std;

struct data {
    int val, ed;
    bool ck;
};

vector <int> adj[N];
deque <data> mq;
int u[N], v[N], c[N], n, m;
int d[N][2];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i] >> c[i];
        adj[u[i]].push_back(i);
        adj[v[i]].push_back(i);
    }
    for (int i = 0; i < N; i++) d[i][0] = d[i][1] = inf;
    for (int i = 0; i < adj[1].size(); i++){
        int ed = adj[1][i];
        d[ed][1 != u[ed]] = 1;
        mq.push_front({1, ed, 1 != u[ed]});
    }
    while (mq.size()){
        data U = mq.front(); mq.pop_front();
        int ed = U.ed, val = U.val, ck = U.ck, x = ((ck) ? u[ed] : v[ed]);
        
        if (val != d[ed][ck]) continue;
        if (x == n) return cout << val << "\n", 0;

        for (int i = 0; i < adj[x].size(); i++){
            int ned = adj[x][i];
            if (d[ned][x != u[ned]] <= val + (c[ed] != c[ned])) continue;
            
            d[ned][x != u[ned]] = val + (c[ed] != c[ned]);
            if (c[ed] != c[ned]) mq.push_back({d[ned][x != u[ned]], ned, x != u[ned]});
            else mq.push_front({d[ned][x != u[ned]], ned, x != u[ned]});
        }
    }
    cout << "-1\n";
}

Submission Info

Judge Result