[ UVa ] 10048 - Audiophobia

• আমাকে কোন একটা শহরের একটা জায়গা থেকে অন্য একটা জায়গায় যেতে হবে । আমি বিভিন্ন রাস্তা ব্যাবহার করে আমার  কাঙ্ক্ষিত জায়গায় যেতে পারি । কিন্তু আমাকে এমন রাস্তা ব্যাবহার করে যেতে হবে যে রাস্তা দিয়ে গেলে আমাকে সবথেকে কম decibels এর শব্দ শুনতে হবে ।  
• এই সমস্যা টি সমাধান করার জন্য আমাদের কে  গ্রাফের ইনফরমেশন দেয়া হবে সেগুলো নিয়ে একটা Minimum Spanning Tree বানাতে হবে । 
• এখন এই MST র উপর query করতে হলে আমাদের কে DFS/BFS চালাতে হবে । 
• এইখান থেকে আমরা যে একটা নোড থেকে অন্য একটা নোডে যাওয়ার রাস্তা পাব তার মধ্যে খুজে দেখব কোন এজের ওয়েট সবথেকে বেশি । সেটাই আমাদের কে প্রিন্ট করেত হবে । 
• যদি কোন রাস্তা না থাকে তবে no path প্রিন্ট করতে হবে । 

কোড :

	/**
	* Problem : 10048 - Audiophobia
	* Verdict : Accepted.
	* Time : 0.050 ms.
	* Writer : Mehadi Hasan Menon.
	* Date : 04.01.17.
	**/
	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <queue>
	using namespace std;
	typedef pair <int, int> ii;
	typedef vector <ii> vii;
	const int mx = 105;
	int father[mx];
	int par[mx];
	int cost[mx][mx];
	struct edge {
	int u, v, w;
	bool operator < (const edge &p) const {
	return w < p.w;
	}
	};
	int find_father(int r)
	{
	if(father[r] == r) {
	return r;
	}
	father[r] = find_father(father[r]);
	return father[r];
	}
	bool is_same_set(int a, int b) {
	return find_father(a) == find_father(b);
	}
	int bfs(int src, int des, vector <vii> g, int n)
	{
	bool vis[n];
	queue <int> Q;
	for(int i = 1; i <= n; i++) {
	vis[i] = false;
	}
	vis[src] = true;
	Q.push(src);
	while(!Q.empty())
	{
	int u = Q.front(); Q.pop();
	if(u == des) {
	return true;
	}
	for(int i = 0; i < g[u].size(); i++)
	{
	ii data = g[u][i];
	int v;
	v = data.first;
	if(vis[v] == false)
	{
	vis[v] = true;
	Q.push(v);
	par[v] = u; // save path
	cost[u][v] = data.second; // save the cost;
	}
	}
	}
	// three is no path :(
	return false;
	}
	int max_weight = 0;
	int path(int src, int des)
	{
	if(des == src) {
	return max_weight;
	}
	max_weight = max(max_weight, cost[ par[des] ][des]);
	path(src, par[des]);
	}
	int main()
	{
	freopen("input.txt", "r+", stdin);
	freopen("output.txt", "r+", stdout);
	int c, s, q, u, v, w;
	int tc;
	tc = 1;
	while(cin >> c >> s >> q)
	{
	if(c == 0 && s == 0 && q == 0) {
	break;
	}
	vector <edge> edge_list;
	for(int i = 0; i < s; i++)
	{
	cin >> u >> v >> w;
	edge data;
	data.u = u;
	data.v = v;
	data.w = w;
	edge_list.push_back(data);
	}
	sort(edge_list.begin(), edge_list.end());
	// make initial set
	for(int i = 1; i <= c; i++) {
	//father[i] == i; // Bug: this line takes my entire day :(
	father[i] = i; // Fixed after one day :P
	}
	int sz = edge_list.size();
	int cnt = 0;
	vector <vii> mst;
	mst.assign(c + 1, vii());
	for(int i = 0; i < sz; i++)
	{
	edge new_edge = edge_list[i];
	int u = find_father(new_edge.u);
	int v = find_father(new_edge.v);
	if(u != v) {
	father[v] = u; // or we can set father[u] = v;
	// create MST
	mst[new_edge.u].push_back(ii(new_edge.v, new_edge.w));
	mst[new_edge.v].push_back(ii(new_edge.u, new_edge.w));
	}
	}
	if(tc > 1) {
	printf("\n");
	}
	int src, des;
	printf("Case #%d\n", tc++);
	for(int i = 0; i < q; i++)
	{
	scanf("%d %d", &src, &des);
	// run BFS on our created MST according to given query
	bool ans = bfs(src, des, mst, c);
	if(ans == true) {
	max_weight = 0;
	path(src, des);
	printf("%d\n", max_weight);
	}
	else {
	printf("no path\n");
	}
	}
	}
	return 0;
	}

view raw 10048.cpp hosted with ❤ by GitHub

হ্যাপি কোডিং :)