poj 1125 Stockbroker Grapevine 代码及分析

今天下午打了第一场省赛选拔赛，八题只AC了三题……

最大的遗憾是碰见一个最短路的水题，就因为英文看了半天，浪费了不少时间，最终迟了一分钟才提交。另外最最大的遗憾就是……我copy了代码，回来在poj提交，居然1Y了……

题目大概是这个意思：按顺序给出各个人与其他人的信息传播所需要时间的关系，建立有向图，求出从哪个人开始传播谣言可以最快让全部人知道。同时，要求出从这个人开始传播开始到最迟收到谣言的人所需要的时间。

下面是我的代码，旁边注有解释：

View Code

1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 #include<math.h>
5 #define MAX 999 //设999为断路
6
7 int s[15][15], t[15][15];
8
9 int check(int n, int a) //最短路算法，求最少时间
10 {
11     int i, j, k;
12     int max;
13
14     for(k=1; k<=n; k++)
15         if(k!=a)
16             for(i=1; i<=n; i++)
17                 for(j=1; j<=n; j++)
18                     if(j!=a)
19                         if(t[i][j]>t[i][k]+t[k][j])t[i][j]=t[i][k]+t[k][j];
20     max=0;
21     for(i=1; i<=n; i++)if(max<t[a][i])max=t[a][i]; //求出从第a个人发布到最后一个人收到的时间差
22
23     return max;
24 }
25
26 void reset(void) //重置数组S
27 {
28     int i, j;
29     for(i=0; i<15; i++)
30     {
31         for(j=0; j<15; j++)
32             s[i][j]=MAX;
33         s[i][i]=0;
34     }
35 }
36
37 void copy(void) //复制数组S到T
38 {
39     int i, j;
40     for(i=0; i<15; i++)
41         for(j=0; j<15; j++)
42             t[i][j]=s[i][j];
43 }
44
45 int main()
46 {
47     int i, j, p, q, min, num;
48     int n, m;
49     int tmp[15];
50
51     memset(tmp, 0, sizeof(tmp)); //这是用来储存各个人发布时所需要的时间的，以便最后挑选出最快那个
52     while(scanf("%d", &n)&&n)
53     {
54         reset();
55         for(i=1; i<=n; i++)
56         {
57             scanf("%d", &m);
58             while(m--)
59             {
60                 scanf("%d%d", &p, &q);
61                 s[i][p]=q;
62             }
63         }
64         for(i=1; i<=n; i++) //遍历各种情况
65         {
66             copy();
67             tmp[i]=check(n, i);
68         }
69         min=999999;
70         for(i=1; i<=n; i++)
71             if(min>tmp[i])min=tmp[i], num=i;
72         if(min==MAX)printf("disjoin\n"); //如果最小路处理完了后还是断路，那么就是disjoin了
73         else printf("%d %d\n", num, min);
74     }
75     return 0;
76 }

written by Lyon