1002 - Country Roads ~ Ankur's Blog

	#include<bits/stdc++.h>
	using namespace std;
	const int INF = 1e9 + 7;
	vector<pair<int,int> > graph[1005];
	vector<int> p,d;
	void dijkstra(int s, int n)
	{
	d.assign(n,INF);
	//p.assign(n, -1);

	d[s] = 0;
	using pii = pair<int,int>;
	priority_queue<pii, vector<pii>, greater<pii>> PQ;

	PQ.push({0,s});

	while(!PQ.empty())
	{
	int v = PQ.top().second;
	int d_v = PQ.top().first;
	PQ.pop();
	if(d_v != d[v]) continue;

	for(auto x: graph[v])
	{
	int to = x.first;
	int len = x.second;
	int mx = max(len, d[v]);
	if(mx < d[to]){
	d[to] = mx;
	PQ.push({d[to], to});
	}
	// cout << to << " "<<len << " "<<d[to]<<endl;
	//d[to] = min(d[to], max(len, d[v]));
	}
	}
	}

	int main()
	{
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	int T;
	scanf("%d", &T);
	for(int cs = 1; cs <= T; cs++)
	{
	int n,m;
	scanf("%d %d", &n, &m);
	d.clear();
	for(int i = 0; i < n; i++)graph[i].clear();
	for(int i = 0; i < m; i++)
	{
	int x,y,z;
	// cin >> x >> y >> z;
	scanf("%d %d %d", &x,&y,&z);
	graph[x].push_back({y,z});
	graph[y].push_back({x,z});
	}
	//cout << "------------------------\n";
	//print();
	int t;
	scanf("%d", &t);
	dijkstra(t,n);
	printf("Case %d:\n",cs);
	for(int i = 0; i < n; i++)
	{
	if(t == i)printf("0\n");
	else if(d[i] ==INF)printf("Impossible\n");
	else
	{
	printf("%d\n", d[i]);
	// cout << w[i][t]<<endl;
	}
	}
	}
	return 0;
	}

Ankur's Blog