亚洲午夜激情网页,欧美国产综合一区二区,免费欧美在线视频

對于蝸牛來說，狂奔雖不代表極速，但展現的卻是一種拼盡全力的姿態........

pku 1797

2009年7月29日

題目鏈接：PKU 1797 Heavy Transportation

分類：最短路的變形

題目分析與算法原型
這道題目也是一個最短路徑的變形，就不細講了，Dijkastra中將判斷語句改成dis[j]=Max(dis[j],Min(dis[u],map[u][j]))就OK了

Code:

1

#include<stdio.h>
2

#define len 1005
3

#define min -1
4

5

int map[len][len],dis[len],visit[len],n,m,t;
6

7

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)map[i][j]=0;
14

else map[i][j]=min;
15

}
16

}
17

int Min(int a,int b)
18

{
19

return a < b ? a : b;
20

}
21

void Dijkastra(int s, int v)//s為源點，v為終點（若有的話）
22

{
23

int i,j;
24

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

{
26

dis[i]=map[s][i];
27

visit[i]=0;
28

}
29

visit[s]=1;
30

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

{
32

int max=min,u;
33

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

if(visit[j]==0&&dis[j]>max)
35

{
36

u=j;
37

max=dis[j];
38

}
39

if(max==min)return;//此語句對于非連通圖是必須的，表示當前已經不存在路徑了
40

if(u==v)return ;//若題目是求從給定某個點到另一個給定的點之間的最短路徑時，加上這句節時
41

visit[u]=1;
42

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

if(visit[j]==0&&map[u][j]!=min)
44

if(dis[j]<Min(dis[u],map[u][j]))dis[j]=Min(dis[u],map[u][j]);
45

}
46

}
47

int main()
48

{
49

int i,k;
50

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

for(k=1;k<=t;k++)
52

{
53

scanf("%d%d",&n,&m);
54

init();
55

for(i=1;i<=m;i++)
56

{
57

int a,b,cost;
58

scanf("%d%d%d",&a,&b,&cost);
59

map[a][b]=cost;
60

map[b][a]=cost;
61

62

}
63

Dijkastra(1,n);
64

printf("Scenario #%d:\n",k);
65

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

}
67

return 0;
68

}
69

posted on 2009-07-29 17:42 蝸牛也Coding 閱讀(392) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。




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

<

2009年8月

>

日

一

二

三

四

五

六

26

27

28

29

30

31

1

2

3

4

5

6

8

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

統計

隨筆 - 78
文章 - 0
評論 - 96
引用 - 0

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

積分 - 95166
排名 - 261

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

pku 1797

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜