久久精品国产亚洲一区二区,国产精品久久久999,欧美精品在线免费

pku 1847

2009年7月24日

題目鏈接：PKU 1847 Tram

分類：最短路

題目分析與算法原型
將需要搬動(dòng)的開關(guān)的節(jié)點(diǎn)的權(quán)值設(shè)為1，不需要搬動(dòng)的開關(guān)設(shè)為0，不可達(dá)的設(shè)為一個(gè)充分大的數(shù)，這樣一來，此題就轉(zhuǎn)換為最短路徑問題了，3種方法（Dijkastra,Floyd以及Bellman-Ford）都可以解決

Code1: （Floyd）

1

#include<stdio.h>
2

#define Len 105
3

#define max 99999999
4

int a[Len][Len],i,j,k,n,A,B,t;
6

void init()
8

{
9

for(i=1;i<=n;i++)
10

for(j=1;j<=n;j++)
11

{
12

if(i==j)a[i][j]=0;
13

else a[i][j]=max;
14

}
15

}
16

int main()
17

{
18

scanf("%d%d%d",&n,&A,&B);
19

init();
20

for(i=1;i<=n;i++)
21

{
22

scanf("%d",&k);
23

for(j=1;j<=k;j++)
24

{
25

scanf("%d",&t);
26

if(j==1)a[i][t]=0;
27

else a[i][t]=1;
28

}
29

}
30

for(k=1;k<=n;k++)
31

for(i=1;i<=n;i++)
32

for(j=1;j<=n;j++)
33

if(a[i][k]+a[k][j]<a[i][j])a[i][j]=a[i][k]+a[k][j];
34

if(a[A][B]==max)printf("-1\n");
36

else printf("%d\n",a[A][B]);
37

return 0;
38

}
39

Code2: (Dijkastra)

1

#include<stdio.h>
2

#include<string.h>
3

#define Len 105
4

#define max 99999999
5

int a[Len][Len],i,j,k,n,A,B,t,flag[Len],dis[Len],min,u;
6

void init()
7

{
8

for(i=1;i<=n;i++)
9

for(j=1;j<=n;j++)
10

{
11

if(i==j)a[i][j]=0;
12

else a[i][j]=max;
13

}
14

}
15

void Dij()
16

{
17

for(i=1;i<=n;i++)dis[i]=a[A][i];
18

flag[A]=1;
19

for(i=1;i<n;i++)
20

{
21

min=max;
22

for(j=1;j<=n;j++)
23

if(flag[j]==0&&dis[j]<min)
24

{
25

u=j;
26

min=dis[j];
27

}
28

if(min==max)return;
29

flag[u]=1;
31

for(j=1;j<=n;j++)
32

if(flag[j]==0&&a[u][j]<max&&dis[u]+a[u][j]<dis[j])
33

dis[j]=dis[u]+a[u][j];
34

}
35

}
36

int main()
37

{
38

scanf("%d%d%d",&n,&A,&B);
39

init();
40

memset(flag,0,sizeof(flag));
41

for(i=1;i<=n;i++)
42

{
43

scanf("%d",&k);
44

for(j=1;j<=k;j++)
45

{
46

scanf("%d",&t);
47

if(j==1)a[i][t]=0;
48

else a[i][t]=1;
49

}
50

}
51

Dij();
52

if(dis[B]==max)printf("-1\n");
53

else printf("%d\n",dis[B]);
54

return 0;
55

}
56

Code3:(Bellman-Ford)

1

#include<stdio.h>
2

#define Len 105
3

#define max 99999999
4

int a[Len][Len],k,n,A,B,t,dis[Len];
6

void init()
8

{
9

int i,j;
10

for(i=1;i<=n;i++)
11

for(j=1;j<=n;j++)
12

{
13

if(i==j)a[i][j]=0;
14

else a[i][j]=max;
15

}
16

}
17

void bellman_ford()
19

{
20

int queue[Len*100]={0},pos=0,fp=0,i;
21

queue[pos++]=A;
22

queue[pos++]=n+1;
23

for(i=1;i<=n;i++)dis[i]=max;
24

dis[A]=0;
25

int N=1;
26

while(queue[fp])
27

{
28

int u;
29

while((u=queue[fp++])==n+1)
30

{
31

if(N++>n+1)return ;
32

queue[pos++]=n+1;
33

}
34

for(i=1;i<=n;i++)
35

{
36

if(i!=u&&a[u][i] < max)
37

{
38

if(dis[i]>dis[u]+a[u][i])
39

{
40

dis[i]=dis[u]+a[u][i];
41

queue[pos++]=i;
42

}
43

}
44

}
45

}
46

}
47

int main()
49

{
50

scanf("%d%d%d",&n,&A,&B);
51

init();
52

int i,j;
53

for(i=1;i<=n;i++)
54

{
55

scanf("%d",&k);
56

for(j=1;j<=k;j++)
57

{
58

scanf("%d",&t);
59

if(j==1)a[i][t]=0;
60

else a[i][t]=1;
61

}
62

}
63

bellman_ford();
64

if(dis[B]==max)printf("-1\n");
65

else printf("%d\n",dis[B]);
66

return 0;
67

}
68

Code4:(Bellman-Ford)

1

#include<stdio.h>
2

#define Len 105
3

#define max 99999999
4

int a[Len][Len],i,j,k,n,A,B,t,dis[Len];
6

void init()
8

{
9

for(i=1;i<=n;i++)
10

for(j=1;j<=n;j++)
11

{
12

if(i==j)a[i][j]=0;
13

else a[i][j]=max;
14

}
15

}
16

void bellman_ford()
18

{
19

int i,j,k;
20

for(i=1;i<=n;i++)dis[i]=max;
21

dis[A]=0;
22

for(i=1;i<n;i++)
23

{
24

for(j=1;j<=n;j++)
25

for(k=1;k<=n;k++)
26

{
27

if(j==k)continue;
28

if(dis[k]>dis[j]+a[j][k])
29

dis[k]=dis[j]+a[j][k];
30

}
31

}
32

}
33

int main()
35

{
36

scanf("%d%d%d",&n,&A,&B);
37

init();
38

for(i=1;i<=n;i++)
39

{
40

scanf("%d",&k);
41

for(j=1;j<=k;j++)
42

{
43

scanf("%d",&t);
44

if(j==1)a[i][t]=0;
45

else a[i][t]=1;
46

}
47

}
48

bellman_ford();
49

if(dis[B]==max)printf("-1\n");
50

else printf("%d\n",dis[B]);
51

return 0;
52

}
53

posted on 2009-07-24 19:07 蝸牛也Coding 閱讀(316) 評(píng)論(2) 編輯收藏引用

評(píng)論

# re: pku 1847 2009-09-10 18:02 Johnnx

if(j==1)a[i][t]=0;
你代碼里的這一句是什么意思，我不太明白？但卻是必須的。能給我解釋一下嗎回復(fù) 更多評(píng)論

# re: pku 1847 2009-09-11 01:37 蝸牛也Coding

Switch in the i-th intersection is initially pointing in the direction of the first intersection listed.
注意題目中的這句話回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

# re: pku 1847 2009-09-10 18:02 Johnnx

# re: pku 1847 2009-09-11 01:37 蝸牛也Coding

pku 1847

評(píng)論

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜