Submission #2860983

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
 
struct State { int dist; int u; int c; };
 
const int N = 100005, M = 200005;
 
int n, m;
vector< pair<int,int> > G[N];
map <int,int> d[N];
 
void dijkstra() {
	deque<State> q;
	q.push_back({0, 1, 0}); d[1][0] = 0;
 
	while(!q.empty()) {
		State f = q.front(); q.pop_front();
		int u = f.u, c = f.c;
		if (f.dist != d[u][c]) continue;
 
		if (!d[u].count(0) || (d[u].count(0) && d[u][0] > f.dist)) {
			d[u][0] = f.dist; q.push_front({f.dist, u, 0});
		}
 
		if (c) {
			int pos = lower_bound(G[u].begin(), G[u].end(), make_pair(c, 0)) - G[u].begin();
			while(pos < G[u].size() && G[u][pos].first == c) {
				int v = G[u][pos].second;
				if (!d[v].count(c) || (d[v].count(c) && d[v][c] > f.dist)) {
					d[v][c] = f.dist; q.push_front({f.dist, v, c});
				}
				++pos;
			}
		} else {
			for (auto e : G[u]) {
				int v = e.second, cc = e.first;
				if (!d[v].count(cc) || (d[v].count(cc) && d[v][cc] > f.dist + 1)) {
					d[v][cc] = f.dist + 1; q.push_back({f.dist + 1, v, cc});
				}
			}
		}
	}
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	while(m--) {
		int u, v, c; cin >> u >> v >> c;
		G[u].push_back(make_pair(c, v));
		G[v].push_back(make_pair(c, u));
	}
	for (int i = 1; i <= n; ++i) {
		sort(G[i].begin(), G[i].end());
	}
	dijkstra();	
 
	if (!d[n].count(0)) cout << -1 << endl; else cout << d[n][0] << endl;
}

Submission Info

Judge Result