find the safest road

杭电1596
其实本题思路还是运用迪杰斯特拉算法，与前面题有所不同的是本题找最大值，这就要注意，在选取过程中，变量的控制；
View Code
 1 //杭电1596
 2 #include<stdio.h>
 3 #include<string.h>
 4 #define M 999999999
 5 #define N 1010
 6 int b[N];
 7 double map[N][N],a[N];
 8 int panduan(double x)
 9 {
10      return x>0?1:0;//实数与零比较
11 }
12 
13 int main()
14 {
15     int n,m,i,j,k,t,x,y;
16     double c,max;
17     while(scanf("%d",&n)!=-1)
18     {
19         for(i=1;i<=n;i++)
20             for(j=1;j<=n;j++)
21                 scanf("%lf",&map[i][j]);
22             scanf("%d",&m);
23             while(m--)
24             {
25                 scanf("%d%d",&x,&y);
26             for(i=1;i<=n;i++)
27                 {
28                     a[i]=0;//将起始的安全系数全部置为零
29                     b[i]=0;
30                 }
31             if(x==y)
32             {
33                 printf("%.2f\n",map[i][j]);//当x,y为同一个城市时，把对应map[][]输出
34                 continue;
35             }
36                 t=k=x;
37                 a[x]=1;
38                 b[x]=1;
39                 int num=1;
40                 while(num<n)
41                 {
42                     max=-1001;
43                     for(i=1;i<=n;i++)//选取安全系数最高路径
44                     {
45                         if(b[i]==0&&map[t][i])
46                         {
47                             c=a[t]*map[t][i];
48                             if(a[i]<c)
49                                 a[i]=c;
50                             if(max<a[i])
51                             {
52                                 max=a[i];
53                                 k=i;
54                             }
55                         }
56                     }
57                     b[k]=1;
58                     if(k==y||t==k)
59                         break;
60                     t=k;
61                     num++;
62                 }
63                 
64                 if(panduan(a[y]))
65                 printf("%.3f\n",a[y]);
66                 else
67                     printf("What a pity!\n");
68             }
69     }
70     return 0;
71 }