|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
#include <iostream> #include <string.h> #include <vector> #include <fstream> #include <map> #define INF 1000000000 using namespace std; int grY[30][30]; int grO[30][30]; int main() { int N,KK,st,dst; char people,roadtyp,ct1,ct2; char start,dest; int energy; // ofstream out; // out.open("out.txt"); while(cin>>N) { if(N==0) break; for(int i=0;i<30;i++) { for(int j=0;j<30;j++) { if(i==j) { grY[i][j]=0; grO[i][j]=0; } else { grY[i][j]=INF; grO[i][j]=INF; } } } while(N--) { cin>>people>>roadtyp>>ct1>>ct2>>energy; if(people=='Y') { grY[(ct1-'A')+1][(ct2-'A')+1]=energy; if(roadtyp=='B') grY[(ct2-'A')+1][(ct1-'A')+1]=energy; } else { grO[(ct1-'A')+1][(ct2-'A')+1]=energy; if(roadtyp=='B') grO[(ct2-'A')+1][(ct1-'A')+1]=energy; } } for (int i = 0; i < 27; i++) { grY[i][i] = 0; grO[i][i] = 0; } cin>>start>>dest; st=(start-'A')+1; dst=(dest-'A')+1; for(int k=1;k<=26;k++) { for(int i=1;i<=26;i++) { for(int j=1;j<=26;j++) { if(grY[i][j]>grY[i][k]+grY[k][j]) grY[i][j] = grY[i][k]+grY[k][j]; if(grO[i][j]>grO[i][k]+grO[k][j]) grO[i][j] = grO[i][k]+grO[k][j]; } } } int MN = INF; for(int i=1;i<27;i++) { if(grY[st][i]==INF || grO[dst][i]==INF) continue; if(MN>grY[st][i]+grO[dst][i]) { MN = grY[st][i]+grO[dst][i]; } } if(MN==INF) { cout<<"You will never meet.\n"; //out<<"You will never meet.\n"; } else { cout<<MN; //out<<MN; for(int i=1;i<27;i++) { if(MN == (grY[st][i]+grO[dst][i])) { cout<<" "<<char((i-1)+'A'); //out<<" "<<char((i-1)+'A')<<" "; } } cout<<"\n"; //out<<"\n"; } } // out.close(); return 0; } |