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
 6int n,m,i,j,flag[len],u;
 7double map[len][len],dis[len];
 8
 9void 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
19void dij(int v0)  //此题求最大路径
20{
21    for(i=1;i<=n;i++)dis[i]=map[v0][i];
22    flag[v0]=1;
23    
24    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
41int 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 阅读(283) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


<2009年7月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜