Skip to main content

[ UVa ] 10171 - Meeting Prof. Miguel

  • এই সমস্যা তে আমাদের কে এমন একটা সিটি বের করতে হবে যে জায়গা তে আমরা প্রফেসারের সাথে দেখা করতে পারব ।  এবং আমাদের খরচ হবে মিনিমাম হবে যদি প্রফেসারে সাথে আমাদের দেখা করা সম্ভব হয় । 
  • এই জন্য আমরা আমাদের অবস্থান থেকে সবচেয়ে কম খরচে কোথাই  কোথাই যেতে পারি সেটা বের করতে হবে । 
  • এরপর প্রফেসর তার অবস্থান থেকে সবচেয়ে কম খরচে কোথাই  কোথাই যেতে পারে সেটা বের করতে হবে । 
  • এখন যে সকল সিটি তে প্রফেসর ও আমরা উভয়ে যেতে পারি সেই সিটি গুলো একটা ভেক্টরে জমা রাখতে হবে । 
  • ভেক্টরের যে সিটির খরচ সবচেয়ে কম হবে । সেটই আমাদের ও প্রফেসসের মিটিং করা জন্য সবচেয়ে ভাল জায়গা এবং  সেটাই প্রিন্ট করতে হবে । যদি এই রকম একাধিক জায়গা থাকে তবে সবগুলি শহর কে lexicographical order এ প্রিন্ট করতে হবে । 
  • যদি প্রফেসরের সাথে দেখা করা সম্ভব না হয় তবে প্রিন্ট আমরা You will never meet. প্রিন্ট করব ।
কোড :
/**
* Problem : 10171 - Meeting Prof. Miguel
* Verdict : Accepted.
* Writer : Mehadi Hasan Menon.
* Time : Accepted.
**/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int mx = 27;
const int inf = 1000007;
int city_map_y[mx][mx], city_map_m[mx][mx];
void floyd_for_young(int n)
{
for(int k = 0; k < n; k++)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
city_map_y[i][j] = min(city_map_y[i][j], city_map_y[i][k] + city_map_y[k][j]);
}
}
}
}
void floyd_for_old(int n)
{
for(int k = 0; k < n; k++)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
city_map_m[i][j] = min(city_map_m[i][j], city_map_m[i][k] + city_map_m[k][j]);
}
}
}
}
void init(int n)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(i == j) {
city_map_y[i][j] = 0;
city_map_m[i][j] = 0;
}
else {
city_map_y[i][j] = inf;
city_map_m[i][j] = inf;
}
}
}
}
void create_map(int n)
{
char y_or_m, u_or_b, city1, city2;
int cost;
for(int i = 0; i < n; i++)
{
cin.ignore();
scanf("%c %c %c %c %d", &y_or_m, &u_or_b, &city1, &city2, &cost);
int u = city1 - 'A';
int v = city2 - 'A';
// city map for young people.
if(y_or_m == 'Y')
{
if(u_or_b == 'U') {
city_map_y[u][v] = min(cost, city_map_y[u][v]);
}
else {
city_map_y[u][v] = city_map_y[v][u] = min(cost, city_map_y[u][v]);
}
}
// city map for old people.
else
{
if(u_or_b == 'U') {
city_map_m[u][v] = min(cost, city_map_m[u][v]);
}
else {
city_map_m[u][v] = city_map_m[v][u] = min(cost, city_map_m[u][v]);
}
}
}
}
int main()
{
freopen("input.txt", "r+", stdin);
char src, des;
int n;
while(scanf("%d", &n) && n != 0)
{
init(26);
create_map(n);
cin.ignore();
scanf("%c %c", &src, &des);
vector <pair<int, char>> vic;
int u = src - 'A';
int v = des - 'A';
floyd_for_young(26); // find shortest path for me
floyd_for_old(26); // find shortest path for prof.
for(int k = 0; k < 26; k++)
{
// if I can go from src to k and he can go des to k the save the location k;
if(city_map_y[u][k] != inf && city_map_m[v][k] != inf) {
vic.push_back( make_pair(city_map_y[u][k] + city_map_m[v][k], k + 'A') );
}
}
if(vic.size() == 0) {
printf("You will never meet.\n");
}
else
{
sort(vic.begin(), vic.end());
int sz = vic.size();
int ans = vic[0].first;
cout << vic[0].first;
for(int i = 0; i < sz; i++)
{
if(vic[i].first != ans) {
break;
}
cout << " " << vic[i].second;
}
cout << endl;
}
}
return 0;
}
view raw 10171.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