Country Roads - LOJ-1002

 Problem: Country Roads - LOJ-1002

Shortest path problem, 0 থেকে N-1 তম নোডে যাইতে মিনিমাম খরচ বের করতে হবে, কিন্তু একটু আলাদা ভাবে।

হিসাব টা হবে এমন যে,

প্রব্লেমের এক্সাম্পল যদি চিন্তা করি,

0 থেকে 4 যাইতে, হিসাবঃ

0-1 ->cost 2, 1-4-> cost 8, So max cost is 8.

Similarly, 

0-2-4 -> 9

0-3-4 -> 7

From the above cost (8, 9, 7), the minimum cost is 7.

তাহলে আমাদেরকে, ম্যাক্সিমাম থেকে মিনিমাম খরচ টা বের করতে হবে।

Code:

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

const int maxn = 555;

vector< pair > adj[maxn];
void init() {
	for (register int i = 0; i < maxn; i++) {
		adj[i].clear();
	}
}
vector dijkstra(int source) {
	priority_queue< pair, vector< pair >, greater< pair > > pq;
	vectordistance(maxn, -1);
	vectorvisit(maxn, false);

	distance[source] = 0;

	pq.push({ 0, source });

	while (!pq.empty()) {
		int parent = pq.top().second;
		pq.pop();

		if (visit[parent])continue;
		visit[parent] = true;

		for (auto v : adj[parent]) {
			int child = v.first;
			int cost = v.second;
			if ((distance[child] > max(distance[parent], cost) && distance[child] > -1) || distance[child] == -1) {
				distance[child] = max(distance[parent], cost);
				pq.push({ distance[child], child });
			}
		}
	}
	return distance;
}

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

	int t; cin >> t;
	vector distance = dijkstra(t);
	for (int i = 0; i < n; i++) {
		if (distance[i] == -1) {
			cout << "Impossible" << endl;
		}
		else cout << distance[i] << endl;
	}
}

int main() {
	//ctrl+alt+b
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int T = 1; cin >> T;
	for (int __ = 1; __ <= T; __++) {
		cout << "Case " << __ << ":" << endl;
		task();
	}

	return 0;
}