青青热久久综合网伊人,久久精品国产免费,曰曰摸天天摸人人看久久久

PKU 1394 Railroad 題解

最短路徑問題。
把每個點出發的所有路都存下
然后每一個點中按每一個路的出發時間降序排序。
然后就做超多遍最短路徑就可以了

#include<stdio.h>
2

#include<map>
3

#include<string>
4

#include<string.h>
5

#include <stdlib.h>
6

using namespace std;
7

map<string,int>city;
8

struct C{int to,s,t;};
9

C data[100][1000];
10

int l[110],ans[110];
11

char use[110];
12

int cmp(const void * elem1, const void * elem2)
13

{
14

return ((struct C*)elem2)->s - ((struct C*)elem1)->s;
15

}
16

int 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

posted on 2008-07-18 16:43 gong 閱讀(296) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

PKU 1394 Railroad 題解

導航

統計

常用鏈接

留言簿(6)

隨筆檔案

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜