Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1112
Shahriar Manzoor and Miguel A. Revilla (Shanghai, 2005). First meeting after five years of collaboration I have always thought that someday I will meet Professor Miguel, who has allowed me to arrange so many contests. But I have managed to miss all the opportunities in reality. At last with the help of a magician I have managed to meet him in the magical City of Hope. The city of hope has many roads. Some of them are bi-directional and others are unidirectional. Another important property of these streets are that some of the streets are for people whose age is less than thirty and rest are for the others. This is to give the minors freedom in their activities. Each street has a certain length. Given the description of such a city and our initial positions, you will have to find the most suitable place where we can meet. The most suitable place is the place where our combined effort of reaching is minimum. You can assume that I am 25 years old and Prof. Miguel is 40+. Input The input contains several descriptions of cities. Each description of city is started by a integer N, which indicates how many streets are there. The next N lines contain the description of N streets. The description of each street consists of four uppercase alphabets and an integer. The first alphabet is either ‘Y’ (indicates that the street is for young) or ‘M’ (indicates that the road is for people aged 30 or more) and the second character is either ‘U’ (indicates that the street is unidirectional) or ‘B’ (indicates that the street is bi-directional). The third and fourth characters, X and Y can be any uppercase alphabet and they indicate that place named X and Y of the city are connected (in case of unidirectional it means that there is a one-way street from X to Y ) and the last non-negative integer C indicates the energy required to walk through the street. If we are in the same place we can meet each other in zero cost anyhow. Every energy value is less than 500. After the description of the city the last line of each input contains two place names, which are the initial position of me and Prof. Miguel respectively. A value zero for N indicates end of input. Output For each set of input, print the minimum energy cost and the place, which is most suitable for us to meet. If there is more than one place to meet print all of them in lexicographical order in the same line, separated by a single space. If there is no such places where we can meet then print the line ‘You will never meet.’
Sample Input 4 Y U A B 4 Y U C A 1 M U D B 6 M B C D 2 A D 2 Y U A B 10 M U C D 20 A D 0
Sample Output 10 B You will never meet.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
char type,direction,a,b;
int val;
while(scanf("%d",&n), n!=0){
int youngGraph[26][26] = {};
int elderGraph[26][26] = {};
for(int i=0;i < 26;i++)
for(int j=0;j < 26;j++)
youngGraph[i][j] = elderGraph[i][j] = i==j ? 0 : 1e7;
for(int i=0;i < n;i++){
cin >> type >> direction >> a >> b >> val;
a -= 'A';
b -= 'A';
if(type == 'Y'){
youngGraph[a][b] = min(val,youngGraph[a][b]);
if(direction == 'B'){
youngGraph[b][a] = min(val,youngGraph[b][a]);
}
} else {
elderGraph[a][b] = min(val,elderGraph[a][b]);
if(direction == 'B'){
elderGraph[b][a] = min(val,elderGraph[b][a]);
}
}
}
// floyd warshall
for(int k=0;k<26;k++)
for(int i=0;i < 26;i++)
for(int j=0;j < 26;j++){
elderGraph[i][j] = min(elderGraph[i][j], elderGraph[i][k]+elderGraph[k][j]);
youngGraph[i][j] = min(youngGraph[i][j], youngGraph[i][k]+youngGraph[k][j]);
}
int best = INT_MAX;
vector<int> meetings;
cin >> a >> b;
a-='A'; b-='A';
for(int i=0;i < 26;i++)
if(youngGraph[a][i] < 1e7 && elderGraph[b][i] < 1e7){
int cost = youngGraph[a][i]+elderGraph[b][i];
if(cost < best){
best = cost;
meetings.clear();
}
if(cost == best) meetings.push_back(i+'A');
}
if(meetings.empty())
printf("You will never meet.\n");
else{
printf("%d",best);
for(auto& v : meetings)
printf(" %c",v);
printf("\n">;
}
}
} Input
Y U A B 4
Y U C A 1
M U D B 6
M B C D 2
A D
2
Y U A B 10
M U C D 20
A D
0
Output
You will never meet.
Demonstration
UVA Online Judge solution - 10171 - Meeting Prof Miguel - UVA Online Judge solution in C,C++,Java