|
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 |
#include <iostream> #include <algorithm> #include <queue> #include <cstdio> #include <cstring> #include <string> #include <map> #include <vector> using namespace std; struct Schedule{ int to; int start,end; Schedule(int a,int b,int c) { to = a; start = b; end = c; } }; vector<Schedule> vb[101]; int kase=1; map<string,int> mp; char dest_city[1024], start_city[1024]; int earliest_start_time, cityNum; int dist[2400][101];//saves maximum departure time from start void solve() { int st_city = mp[start_city]; int end_city = mp[dest_city]; int reach_time,reach_city; memset(dist,-1,sizeof(dist)); for(int i=0;i<vb[st_city].size();i++) { if(vb[st_city][i].start>=earliest_start_time) { reach_time = vb[st_city][i].end; reach_city = vb[st_city][i].to; dist[reach_time][reach_city]= max( dist[reach_time][reach_city] , vb[st_city][i].start ); } } for(int i=earliest_start_time;i<2400;i++) { for(int j=0;j<cityNum;j++) { if(dist[i][j]==-1) continue; for(int k=0;k<vb[j].size();k++) { if(vb[j][k].start>=i) { dist[vb[j][k].end][vb[j][k].to] = max(dist[vb[j][k].end][vb[j][k].to],dist[i][j]); } } } if(dist[i][end_city]!=-1) { printf("%04d %04d\n",dist[i][end_city],i); return; } } printf("No connection\n"); } int main() { int prev_time, prev_city, cur_time, cur_city; int trainNum, noOfCities, t, arrival_time; char str[1024]; while(scanf("%d",&cityNum)&&cityNum!=0) { mp.clear(); for(int i=0;i<cityNum;i++) { scanf("%s",str); mp[str]=i; vb[i].clear(); } scanf("%d",&trainNum); for(int i=1;i<=trainNum;i++) { scanf("%d",&noOfCities); for(int j=0;j<noOfCities;j++) { scanf("%d %s",&arrival_time,str); if(j>0 && arrival_time>prev_time) { cur_time = arrival_time; cur_city = mp[str]; vb[prev_city].push_back(Schedule(cur_city,prev_time,cur_time)); } prev_time = arrival_time; prev_city = mp[str]; } } scanf("%d %s %s",&earliest_start_time,start_city,dest_city); solve(); } return 0; } |