色偷偷88欧美精品久久久,久久精品成人免费看,久久婷婷色综合一区二区

pku 2387

2009年7月24日

題目鏈接：PKU 2387 Til the Cows Come Home

分類：簡單最短路

題目分析與算法原型
這道題也是一道較簡單的最短路徑問題，不過這題目有重邊（看了討論才知道），意思是說輸入的路徑中，存在一些起點和終點都相同但長度卻不同的路徑，這個時候只要保存最小的長度作為權值即可，其他沒什么,Dijkastra就行了

Code:

1

#include<stdio.h>
2

#include<string.h>
3

#define len 1005
4

#define max 0x7fffffff
5

int t,n,i,j,map[len][len],dis[len],flag[len],u;
7

void dij(int v0)
9

{
10

for(i=1;i<=n;i++)dis[i]=map[v0][i];
11

flag[v0]=1;
12

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

{
14

int min=max;
15

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

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

{
18

u=j;
19

min=dis[j];
20

}
21

if(min==max)return;
22

flag[u]=1;
24

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

if(flag[j]==0&&map[u][j]<max&&dis[u]+map[u][j]<dis[j])
26

dis[j]=dis[u]+map[u][j];
27

}
28

}
30

void init()
32

{
33

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

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

{
36

if(i==j)map[i][j]=0;
37

else map[i][j]=max;
38

}
39

}
40

int main()
42

{
43

while(scanf("%d%d",&t,&n)!=EOF)
44

{
45

int a,b,l;
46

init();
47

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

for(i=0;i<t;i++)
49

{
50

scanf("%d%d%d",&a,&b,&l);
51

if(l<map[a][b])
52

{
53

map[a][b]=l;
54

map[b][a]=l;
55

}
56

}
57

dij(n);
58

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

}
60

return 0;
61

}
62

posted on 2009-07-24 20:12 蝸牛也Coding 閱讀(266) 評論(0) 編輯收藏引用

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



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

2009年7月

日

一

二

三

四

五

六

統計

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

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

積分 - 93680
排名 - 260

pku 2387

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜