MemoryGarden's Blog

努力 -----------大能猫

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks

最短路径 floyd

http://acm.pku.edu.cn/JudgeOnline/problem?id=1125


题目的意思比较难懂。。。我还是别人看明白了来问我,我才知道题意的,要不然我也看不明白,英语不好。

就是股票经纪人,u, v  两个点, 然后意思是传播谣言需要的时间,所以是每对点的最短路径。

从中选出最快完成的,也就是求出图中每个点到图中其余点的最短路径的最大值,取最小



 1 #include <stdio.h>
 2 #include <string.h>
 3 #define max 102
 4 int main(){
 5     int i, j, t, u, v, w, k, m, n, D[max][max], v2, p, ok;
 6     while(scanf("%d"&m), m){
 7         ok = 0;
 8         for(i = 0; i < max; i++)
 9             for(j = 0; j < max; j++)
10                 D[i][j] = max;
11         for(u = 1; u <= m; u++){
12             scanf("%d"&t);
13             for(i = 1; i <= t; i++){
14                 scanf("%d%d"&v, &w);
15                 D[u][v] = w;
16             }
17         }
18         for(k = 1; k <= m; k++)
19             for(i = 1; i <= m; i++)
20                 for(j = 1; j <= m; j++)
21                     if(D[i][k] + D[k][j] < D[i][j] && i != j)
22                         D[i][j] = D[i][k] + D[k][j];
23         v2 = max;
24         for(i = 1; i <= m; i++){
25             v = 0;
26             for(j = 1; j <= m; j++)
27                 if(i != j && D[i][j] > v)v = D[i][j];
28             if(v != max){
29                 ok = 1;
30                 if(v < v2){
31                     v2 = v;
32                     p = i;
33                 }
34             }
35         }
36         printf("%d %d\n", p, v2);
37     }
38     return 0;
39 }

posted on 2008-09-04 00:24 memorygarden 阅读(661) 评论(0)  编辑 收藏 引用 所属分类: 报告

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