Submission #2861023

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int inf = 2e9;

int n, m;
vector<int> adj[N], col[N], imp[N];
vector<int> f[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int u, v, c; cin >> u >> v >> c;
		col[u].push_back(c), col[v].push_back(c);
		imp[u].push_back(adj[v].size()), imp[v].push_back(adj[u].size());
		adj[u].push_back(v), adj[v].push_back(u); 
	}
	
	for (int i = 1; i <= n; ++i) {
		f[i].assign(adj[i].size(), (i == 1 ? 1 : inf));
	}
	
	priority_queue<pair<int, pair<int,int> > , vector<pair<int, pair<int,int> > >, greater<pair<int, pair<int,int> > > > pq;
	for (int i = 0; i < adj[1].size(); ++i) pq.push({1, {1, i}});
	
	while (!pq.empty()) {
		auto cur = pq.top(); pq.pop();
		int u = cur.second.first, id = cur.second.second;
		if (f[u][id] != cur.first) continue;
		for (int i = 0; i < adj[u].size(); ++i) {
			int nu = adj[u][i], nid = imp[u][i];
			int add = 1;
			if (col[u][id] == col[nu][nid]) add = 0;
			if (f[nu][nid] > f[u][id] + add) {
				f[nu][nid] = f[u][id] + add;
				pq.push({f[nu][nid], {nu, nid}});
			}
		} 
	} 
	
	int res = inf;
	for (int i = 0;i < adj[n].size(); ++i) res = min(res, f[n][i]);
	if (res == inf) res = -1;
	cout << res << '\n';
} 

Submission Info

Judge Result