HDU 1596 最短路变形

这道题怎么都是TLE，报警了，先放在这

http://acm.hdu.edu.cn/showproblem.php?pid=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!
";
75                     }
76           }
77           return 0;
78 }

ac了，1482MS

 1 #include <cstdio>
 2 using namespace std;
 3 const int L = 1010;
 4 const int INF = 1<<27;
 5 
 6 double map[L][L];
 7 int vis[L];
 8 double dis[L];
 9 
10 int n,m;
11 
12 void Dijkstra(int s)
13 {
14           int i,j,k;
15           double max;
16           for(i = 1;i<=n;i++)
17           {
18                     dis[i] = map[s][i];
19                     vis[i] = 0;
20           }
21 
22           vis[s] = 1;
23           dis[s] = 0;
24 
25           for(i = 1;i<=n;i++)
26           {
27                     max = 0;
28                     for(j = 1;j<=n;j++)
29                     {
30                               if(dis[j]>max && !vis[j])
31                               {
32                                         k = j;
33                                         max = dis[j];
34                               }
35                     }
36 
37                     vis[k] = 1;
38 
39                     for(j = 1;j<=n;j++)
40                     {
41                               if(dis[j] < max*map[k][j] && !vis[j])
42                               {
43                                         dis[j] = max*map[k][j];
44                               }
45                     }
46           }
47 }
48 
49 void init()
50 {
51           int i,j;
52           for(i = 1;i<=n;i++)
53           {
54 
55                     for(j = 1;j<=n;j++)
56                     {
57                               scanf("%lf",&map[i][j]);
58                     }
59           }
60 }
61 
62 
63 int main()
64 {
65           while(scanf("%d",&n)!=EOF)
66           {
67                     int r,t;
68 
69                     init();
70 
71                     scanf("%d",&r);
72                     while(r--)
73                     {
74                               int a,b;
75                               scanf("%d%d",&a,&b);
76                               Dijkstra(a);
77                               if(dis[b])
78                                         printf("%.3lf
",dis[b]);
79                               else
80                                         printf("What a pity!
");
81                     }
82 
83           }
84 
85           return 0;
86 }