婷婷久久综合九色综合九七,亚洲国产精品人久久,国产精品免费看久久久

pku 2472

2009年7月25日

題目鏈接：PKU 2472 106 miles to Chicago

分類：最短路變形

題目分析與算法原型
其實這道題目的本質是一個“最短路徑”問題，就用Dijkastra算法即可解決，不過，需要注意的是運用時，我們不再求最小的代價而是求最大的代價，即為最大的不被逮捕的概率，所以需要對Dijkastra做一些改進，除了將最短改成最大的之外，還要將“+”改成“*”

Code:

1

#include<stdio.h>
2

#include<string.h>
3

#define min -1
4

#define len 105
5

int n,m,i,j,flag[len],u;
7

double map[len][len],dis[len];
8

void init()
10

{
11

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

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

{
14

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

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

}
17

}
18

void dij(int v0) //此題求最大路徑
20

{
21

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

flag[v0]=1;
23

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

{
26

double max=min;
27

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

if(flag[j]==0&&dis[j]>max)
29

{
30

u=j;
31

max=dis[j];
32

}
33

if(max==min)return ;
34

flag[u]=1;
35

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

if(flag[j]==0&&map[u][j]>min&&dis[u]*map[u][j]>dis[j])
37

dis[j]=dis[u]*map[u][j];
38

}
39

}
40

int main()
42

{
43

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

{
45

scanf("%d",&m);
46

init();
47

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

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

{
50

int a,b;
51

double p;
52

scanf("%d%d%lf",&a,&b,&p);
53

if(p>map[a][b])
54

{
55

map[a][b]=p/100;
56

map[b][a]=p/100;
57

}
58

}
59

dij(1);
60

printf("%.6lf percent\n",dis[n]*100);
61

}
62

return 0;
63

}
64

posted on 2009-07-25 14:50 蝸牛也Coding 閱讀(249) 評論(0) 編輯收藏引用

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



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

pku 2472

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜