Skip to main content

[ UVa ] 341 - Non-Stop Travel

  • Floyd Warshall's  এলগরিদম ব্যবহার করে খুব সহজেই এই সমস্যা সমাধান করা যায় । 
  • আমাদের ইনপুট গ্রাফে যদি u থেকে v তে যাওয়ার জন্য একবার টাইম দেয়া থাকল ২০ সেকেন্ড পরে আবার u থেকে v তে যাওয়ার টাইম দেয়া থাকল ৩০ সেকেন্ড । সেই ক্ষেত্রে আমাদের কে মিনিমাম টাইম অর্থাৎ ২০ সেকেন্ড কে নিতে হবে । 
কোড :
/**
* Problem : 341 - Non-Stop Travel.
* Verdict : Accepted.
* Writer : Mehadi Hasan Menon.
* Time : 0.00 ms.
**/
#include <iostream>
#include <cstdio>
using namespace std;
const int inf = 100000007;
int region[12][12];
int p[12][12];
void floyd_warshall(int node)
{
for(int k = 1; k <= node; k++)
{
for(int i = 1; i <= node; i++)
{
for(int j = 1; j <= node; j++)
{
if(region[i][k] + region[k][j] < region[i][j])
{
region[i][j] = region[i][k] + region[k][j];
p[i][j] = p[i][k];
}
}
}
}
}
void print_path(int i, int j)
{
printf(" %d", i);
while(i != j)
{
i = p[i][j];
printf(" %d", i);
}
}
int main()
{
freopen("input.txt", "r+", stdin);
int ni, streets, u, v, time, tc;
tc = 1;
while(scanf("%d", &ni) && ni != 0)
{
for(int i = 1; i <= ni; i++)
{
for(int j = 1; j <= ni; j++)
{
region[i][j] = inf;
}
}
for(u = 1; u <= ni; u++)
{
scanf("%d", &streets);
for(int i = 0; i < streets; i++)
{
scanf("%d %d", &v, &time);
// IMPORTANT :D
region[u][v] = min(region[u][v], time);
p[u][v] = v;
}
}
floyd_warshall(ni);
int src, des;
scanf("%d %d", &src, &des);
printf("Case %d: Path =", tc++);
print_path(src, des);
printf("; %d second delay\n", region[src][des]);
}
return 0;
}
view raw 341.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 টাইপ করেন । এখন নতুন পাসওয়ার্ড দিয়ে লগইন করেন। পুনশ্চ : যদি আপনার উইন্ডোজ এর সাথে ডুয়েল বুট করা থাকে তবে এই প্রক্রিয়া কাজ করবে না ।
  Good becomes great, bad becomes worse. A strong man who has known power all his life can lose respect for that power, but a weak man knows the value of strength and knows compression