做完这道题感觉自己 Floyd 白学了
#include <bits/stdc++.h>
const int maxn = 250;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long ll;
int n, m;
int maps[maxn][maxn];
int times[maxn];
int main()
{
scanf("%d%d", &n, &m);
for(int i=0; i<n; i++){
scanf("%d", ×[i]);
for(int j=0; j<n; j++){
maps[i][j] = inf;
}
maps[i][i] = 0;
}
for(int i=0; i<m; i++){
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
maps[a][b] = maps[b][a] = w;
}
int q, k = 0;
scanf("%d", &q);
for(int i=0; i<q; i++){
int x, y, t;
scanf("%d%d%d", &x, &y, &t);
while(k<n && t>=times[k]){ //判断是否要重建
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(maps[i][j] > maps[i][k] + maps[k][j])
maps[i][j] = maps[i][k] + maps[k][j];
}
}
k++;
}
if(x>=k || y>=k) //还没重建完成
printf("-1
");
else{
if(maps[x][y] == inf)
printf("-1
");
else
printf("%d
", maps[x][y]);
}
}
return 0;
}