pku 3615

2009年7月26日 星期日

题目链接：PKU 3615 Cow Hurdles 

分类：最短路变形

题目分析与算法原型
        其实本题就是Floyd的一个变形而已，将Floyd中的判断条件改成  if(Max(map[i][k],map[k][j])<map[i][j])map[i][j]=Max(map[i][k],map[k][j])即可.........

Code: 
 
1#include<stdio.h>
 2#define len 305
 3#define max 1000000000
 4
 5int n,m,t,map[len][len],res[len][len];
 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]=max;
15        }
16}
17
18int Max(int a,int b)
19{
20    return a>b?a:b;
21}
22
23int main()
24{
25    int i,j,k;
26    while(scanf("%d%d%d",&n,&m,&t)!=EOF)
27    {
28        init();
29        for(i=1;i<=m;i++)
30        {
31            int s,e,h;
32            scanf("%d%d%d",&s,&e,&h);
33            if(h<map[s][e])map[s][e]=h;
34        }
35
36        for(k=1;k<=n;k++)
37            for(i=1;i<=n;i++)
38                for(j=1;j<=n;j++)
39                {
40                    int t=Max(map[i][k],map[k][j]);
41                    if(t<map[i][j])map[i][j]=t;
42                }
43
44        for(i=1;i<=t;i++)
45        {
46            int a,b;
47            scanf("%d%d",&a,&b);
48            if(map[a][b]<max)printf("%d\n",map[a][b]);
49            else printf("-1\n");
50        }
51    }
52    return 0;
53}
54

posted on 2009-07-26 21:47 蜗牛也Coding 阅读(254) 评论(0)  编辑 收藏 引用


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


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

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜