Skip to main content

[ 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

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

Comments

Popular posts from this blog

উবুন্টুতে রুট পাসওয়ার্ড ভুলে তা রিকভার করার উপায় ।

যদি কেউ রুট পাসওয়ার্ড ভুলে যান তাহলে নিচের কাজ গুলো করে নতুন পাসওয়ার্ড সেট করতে পারবেন: প্রথমে পিসি রিস্টার্ট দিন । দিয়ে UP/DOWN করে kernel version সিলেক্ট করে e চাপুন । ব্ল্যাক Screen আসবে এবার একটা Space দিয়ে লিখুন “Single” [ Enter ] এরপর b চাপুন ফলাফল : লিনাক্সের Single user Mood এ চলে আসছেন । এখন লিখুন passwd root [ Enter ] এখন নতুন পাসওয়ার্ড খানা টাইপ করেন [ এন্টার ] আবার টাইপ করেন [ এন্টার ] কাজ শেষ , এবার reboot টাইপ করেন । এখন নতুন পাসওয়ার্ড দিয়ে লগইন করেন। পুনশ্চ : যদি আপনার উইন্ডোজ এর সাথে ডুয়েল বুট করা থাকে তবে এই প্রক্রিয়া কাজ করবে না ।

Fix The BIOS in this system is not fully ACPI compliant in Windows 7

এই সমস্যা সমাধান করার জন্য আপনি নিচের ধাপ গুলো অনুসরণ করুন। ধাপ ১ :  আপানর  কম্পিউটার এ উইন্ডোজ এর ডিস্ক থেকে বুট করুন । নীচের মত উইন্ডো আসলে Shift + F10 চাপুন । এর ফলে কমান্ড প্রম্প্ট ওপেন হবে। ধাপ ২ : এখন CMD তে নিচের কমান্ড গুলি ধারবাহিক ভাবে লিখুন C: bootrec /FixMbr bootrec /FixBoot bootrec /RebuildBcd exit  এখানে  C হলো যে ড্রাইভ এ উইন্ডোজ দেয়া আছে।  আপনার যদি অন্য কোনো ড্রাইভ ( D, E, F, ..... ) এ উইন্ডোজ দেয়া থাকে তবে আপনাকে C এর জায়গায় সেই ড্রাইভ এর নাম লিখতে হবে।  উপরের সব কমান্ড যদি সঠিক ভাবে বিল্ড হয় তবে আপনি আপনার কম্পিউটার রিস্টার্ট দিন।  দেখবেন আপনার সমস্যা সমাধান হয়ে গেছে :D