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
 5int map[len][len],dis[len],visit[len],n,m,t;
 6
 7void 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}
17int Min(int a,int b)
18{
19    return a < b ? a : b;
20}
21void 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}
47int 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 阅读(326) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年8月>
日一二三四五六
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜