1 #include <iostream> 2 #include <cstdio> 3 #include <map> 4 #include <iomanip> 5 #include <string> 6 #include <cstring> 7 #include <algorithm> 8 using namespace std; 9 10 const int MAXN=105;11 const int MAXM=120000;12 const int inf=90000000;13 int head[MAXN];14 struct e{15     int u,v;16     int depart,arrival;17     int next;18 }edge[MAXM];19 int tot,n,m,limit;20 int start_city,des_city;21 string start,destin;22 int timeh[105][2450];23 24 void addedge(int u,int v,int de,int ar){25     edge[tot].u=u;26     edge[tot].v=v;27     edge[tot].depart=de;28     edge[tot].arrival=ar;29     edge[tot].next=head[u];30     head[u]=tot++;31 }32 33 void slove(){34     for(int e=head[start_city];e!=-1;e=edge[e].next){35         if(edge[e].depart>=limit){36             timeh[edge[e].v][edge[e].arrival]=edge[e].depart;37         }38     }39     for(int i=0;i<=2400;i++){40         for(int j=1;j<=n;j++){41             if(timeh[j][i]!=-1){42                 for(int e=head[j];e!=-1;e=edge[e].next){43                     if(i<=edge[e].depart){44                         timeh[edge[e].v][edge[e].arrival]=max(timeh[edge[e].v][edge[e].arrival],timeh[j][i]);45                     }46                 }47             }48         }49     }50     for(int i=0;i<=2400;i++){51         if(timeh[des_city][i]!=-1){52             cout << "Departure " << setw(4) << setfill(‘0‘);53             cout << timeh[des_city][i] << " " << start << endl;54             cout << "Arrival   " << setw(4) << setfill(‘0‘);55             cout << i << " " << destin << endl;56             return ;57         }58     }59     cout << "No connection" << endl;60 }61 62 int main(){63     string station,pre,cur;64     int cas=0;int T,pretime,curtime,u,v,train;65     scanf("%d",&T);66     while(T--){67         cas++; tot=0;68         memset(head,-1,sizeof(head));69         memset(timeh,-1,sizeof(timeh));70         map<string,int>city;71         scanf("%d",&n);72         for(int i=1;i<=n;i++){73             cin>>station;74             city[station]=i;75         }76         scanf("%d",&train);77         while(train--){78             scanf("%d",&m);79             for(int i=1;i<=m;i++){80                 cin>>curtime>>cur;81                 if(i>1){82                     u=city[pre];83                     v=city[cur];84                     addedge(u,v,pretime,curtime);85                 }86                 pre=cur;87                 pretime=curtime;88             }89         }90         cin>>limit>>start>>destin;91         start_city=city[start]; des_city=city[destin];92          cout << "Scenario " << cas << endl;93         slove();94         cout << endl;95     }96     return 0;97 }