- এই সমস্যা তে আমাদের কে এমন একটা সিটি বের করতে হবে যে জায়গা তে আমরা প্রফেসারের সাথে দেখা করতে পারব । এবং আমাদের খরচ হবে মিনিমাম হবে যদি প্রফেসারে সাথে আমাদের দেখা করা সম্ভব হয় ।
- এই জন্য আমরা আমাদের অবস্থান থেকে সবচেয়ে কম খরচে কোথাই কোথাই যেতে পারি সেটা বের করতে হবে ।
- এরপর প্রফেসর তার অবস্থান থেকে সবচেয়ে কম খরচে কোথাই কোথাই যেতে পারে সেটা বের করতে হবে ।
- এখন যে সকল সিটি তে প্রফেসর ও আমরা উভয়ে যেতে পারি সেই সিটি গুলো একটা ভেক্টরে জমা রাখতে হবে ।
- ভেক্টরের যে সিটির খরচ সবচেয়ে কম হবে । সেটই আমাদের ও প্রফেসসের মিটিং করা জন্য সবচেয়ে ভাল জায়গা এবং সেটাই প্রিন্ট করতে হবে । যদি এই রকম একাধিক জায়গা থাকে তবে সবগুলি শহর কে lexicographical order এ প্রিন্ট করতে হবে ।
- যদি প্রফেসরের সাথে দেখা করা সম্ভব না হয় তবে প্রিন্ট আমরা You will never meet. প্রিন্ট করব ।
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 : 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; | |
} |
Comments
Post a Comment