最短路徑問題。
把每個點(diǎn)出發(fā)的所有路都存下
然后每一個點(diǎn)中按每一個路的出發(fā)時間降序排序。
然后就做超多遍最短路徑就可以了
1
#include<stdio.h>
2#include<map>
3#include<string>
4#include<string.h>
5#include <stdlib.h>
6using namespace std;
7map<string,int>city;
8
struct C
{int to,s,t;};
9C data[100][1000];
10int l[110],ans[110];
11char use[110];
12int cmp(const void * elem1, const void * elem2)
13{
14
return ((struct C*)elem2)->s - ((struct C*)elem1)->s;
15
}
16int main()
17{
18 //freopen("railroad.in","r",stdin);
19 //freopen("railroad.out","w",stdout);
20 int SS,TT,n,i,j,k,TTT,TI,s,t,NO,begin,totle,min,KK=0;
21 string str,S,T;
22 char name[1000],name1[1000],name2[1000];
23 while(scanf("%d",&n),n)
24
{
25 totle=1000000;
26 memset(l,0,sizeof(l));
27 city.clear();
28 for(i=0;i<n;i++)
29 {
30 scanf("%s",name);
31 str=name;
32 city[str]=i;
33
}
34 scanf("%d",&TTT);
35 while(TTT--)
36 {
37 scanf("%d",&TI);
38 scanf("%d%s",&s,name);
39 S=name;SS=city[S];
40 while(--TI)
41 {
42 scanf("%d%s",&t,name);
43 T=name;TT=city[T];
44 data[SS][l[SS]].to=TT;
45 data[SS][l[SS]].s=s;
46 data[SS][l[SS]].t=t;
47 l[SS]++;
48 SS=TT;s=t;
49 }
50 }
51 for(i=0;i<n;i++)qsort(data[i],l[i],sizeof(C),cmp);
52 /**//*
53 for(i=0;i<n;i++)
54 {
55 for(j=0;j<l[i];j++)printf("%d ",data[i][j].s);
56 printf("\n");
57 }
58 */
59 scanf("%d",&s);
60 scanf("%s",&name1);S=name1;SS=city[S];
61 scanf("%s",&name2);T=name2;TT=city[T];
62 for(i=0;i<l[SS];i++)
63 {
64 if(data[SS][i].s<s)break;
65 memset(use,0,sizeof(use));
66 memset(ans,1,sizeof(ans));
67 //printf("asdasd%d\n",ans[100]);
68 ans[SS]=data[SS][i].s;
69 for(k=1;k<n;k++)
70 {
71 min=1000000;
72 for(j=0;j<n;j++)
73 if(!use[j]&&ans[j]!=ans[100]&&ans[j]<min)
74 {
75 min=ans[j];
76 NO=j;
77 }
78 if(min==1000000)break;
79 use[NO]=1;
80 for(j=0;j<l[NO];j++)
81 if(!use[data[NO][j].to])
82 {
83 if(data[NO][j].s<ans[NO])break;
84 if(data[NO][j].t<ans[data[NO][j].to])ans[data[NO][j].to]=data[NO][j].t;
85 }
86 }
87 if(ans[TT]<totle)
88 {
89 begin=ans[SS];
90 totle=ans[TT];
91 }
92 }
93 printf("Scenario #%d\n",++KK);
94 if(totle==1000000)printf("No connection\n");
95 else
96 {
97 printf("Departure ");
98 if(begin<1000)printf("0");
99 else if(begin<100)printf("00");
100 else if(begin<10)printf("000");
101 printf("%d ",begin);
102 printf("%s\n",name1);
103 printf("Arrival ");
104 begin=totle;
105 if(begin<1000)printf("0");
106 else if(begin<100)printf("00");
107 else if(begin<10)printf("000");
108 printf("%d ",begin);
109 printf("%s\n",name2);
110 }
111 printf("\n");
112
113 }
114}
115
116