Floyd--P1119 灾后重建

题目给定村庄建设的时间是从小到大排列的（*不用离散化了）。对于第一次查询，从村庄1开始，一直到第一个村庄未建成开始下一次查询（此时后面的村庄肯定都没建成），每次不断从上一个未建成的村庄一直更新到下一个未建成的村庄（以此保证更新的村庄已建设完毕），直到最后一次查询。

*floyd的代码：

1 for(int i=0;i<n;i++)
2                     for(int j=0;j<n;j++)
3                         dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);

那这道题的代码就是：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 int const maxn=1000;
 8 int const INF=1e9; 
 9 int dist[maxn][maxn];
10 int n,m; 
11 int st,ed,tt;
12 int t[50005];
13 int main(){    
14     int a,b,x,s,ans;    
15     memset(dist,INF,sizeof(dist));
16     memset(t,INF,sizeof(t));
17     scanf("%d %d",&n,&m);     
18     for (int i = 0;i < n;i++)
19         scanf ("%d",&t[i]);
20         for(int i = 0;i < n;i++)            
21         for(int j = 0;j < n;j++)                
22             dist[i][j] = (i == j ? 0 : INF);        
23         while(m--)        
24         {            
25             scanf("%d %d %d",&a,&b,&x);            
26             if(x < dist[a][b])        
27                 dist[a][b] = dist[b][a] = x;        
28             }        
29         int p;
30         scanf ("%d",&p);
31         int k;
32         k=0;
33         while (p--)
34         {
35             scanf("%d %d %d",&st,&ed,&tt);               
36             while(t[k]<=tt&&k<n)
37             {
38                 for(int i=0;i<n;i++)
39                     for(int j=0;j<n;j++)
40                         dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
41                 k++;
42             }
43             if(dist[st][ed]==INF||t[st]>tt||t[ed]>tt) printf ("-1
");
44             else printf ("%d
",dist[st][ed]);
45         }
46     return 0;
47 }