- আমাকে কোন একটা শহরের একটা জায়গা থেকে অন্য একটা জায়গায় যেতে হবে । আমি বিভিন্ন রাস্তা ব্যাবহার করে আমার কাঙ্ক্ষিত জায়গায় যেতে পারি । কিন্তু আমাকে এমন রাস্তা ব্যাবহার করে যেতে হবে যে রাস্তা দিয়ে গেলে আমাকে সবথেকে কম decibels এর শব্দ শুনতে হবে ।
- এই সমস্যা টি সমাধান করার জন্য আমাদের কে গ্রাফের ইনফরমেশন দেয়া হবে সেগুলো নিয়ে একটা Minimum Spanning Tree বানাতে হবে ।
- এখন এই MST র উপর query করতে হলে আমাদের কে DFS/BFS চালাতে হবে ।
- এইখান থেকে আমরা যে একটা নোড থেকে অন্য একটা নোডে যাওয়ার রাস্তা পাব তার মধ্যে খুজে দেখব কোন এজের ওয়েট সবথেকে বেশি । সেটাই আমাদের কে প্রিন্ট করেত হবে ।
- যদি কোন রাস্তা না থাকে তবে no path প্রিন্ট করতে হবে ।
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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; | |
} |
হ্যাপি কোডিং :)
Comments
Post a Comment