HDU 1596 最短路变形

 1 #include <iostream>
 2 #include <iomanip>
 3 using namespace std;
 4 
 5 #define MAXVEX 1001
 6 
 7 double matrix[MAXVEX][MAXVEX];
 8 double D[MAXVEX];
 9 
10 int n;
11 
12 void Dijkstral(int v0)
13 {
14           int v,w,k=1;
15           double max;
16           int final[MAXVEX];
17 
18           for(int i = 1;i<=n;i++)
19           {
20                     D[i] = matrix[v0][i];
21                     final[i] = 0;
22           }
23 
24           final[v0] = 1;
25 
26           for(v=1;v<=n;v++)
27           {
28                     max = -1;
29                     for(w=1;w<=n;w++)
30                     {
31                               if(D[w]>max && !final[w])
32                               {
33                                        max = D[w];
34                                        k = w;
35                               }
36                     }
37 
38                     final[k] = 1;
39 
40                     for(w=1;w<=n;w++)
41                     {
42                               if(max*matrix[k][w]>D[w] && !final[w])
43                               {
44                                         D[w]=max*matrix[v][w];
45                               }
46                     }
47           }
48 
49 }
50 
51 
52 int main()
53 {
54           while(cin>>n)
55           {
56                     for(int i = 1;i<=n;i++)
57                     {
58                               for(int j = 1;j<=n;j++)
59                                         cin>>matrix[i][j];
60                     }
61 
62                     int m;
63                     cin>>m;
64                     while(m--)
65                     {
66                               int a,b;
67                               cin>>a>>b;
68 
69                               Dijkstral(a);
70 
71                               if(D[b])
72                                         cout<<fixed<<setprecision(3)<<D[b]<<endl;
73                               else
74                                         cout<<"What a pity!\n";
75                     }
76           }
77           return 0;
78 }