https://www.luogu.com.cn/problem/P1119
题目中要求是查询多个点的最短距离，所以使用Floyd算法实现，而且要真正理解floyd算法的实质
for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(e[i][j]>e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j];
其实最外层循环就是这个意思：先把1号节点取出来，用内层循环来看1号节点是否能有效缩短i号节点到j号节点的最短距离（i经过1号节点后再到j号节点比i直接到j近）
接着取出2号节点，3号节点……直到将所有的节点全部检验完毕，距离的二维数组中保存的就是各个i节点到j节点的最短路径距离。
而题目中的重建时间（从小到大）则正是floyd算法最外层循环的一种隐式的等价，首先查看输入的查询数据中的时间，如果查询时间大于0号城镇的重建时间（题目是从0到n-1），则可以将0号节点取出，看是否能有效缩短i号节点到j号节点的最短距离，接着再比较1号城镇的重建时间与查询数据中的时间大小，一直到某个节点的重建时间比查询数据中的时间大（或者n个节点全部比较完毕），“最外层循环”结束。
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; #define MAX 210 #define INF 99999999 int edges[MAX][MAX]; int n, m,q; int t[MAX]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); cin >> n >> m; fill(edges[0], edges[0] + MAX*MAX, INF); for (int i = 0; i < n; i++) cin >> t[i]; for (int i = 0; i < m; i++) { int x, y,z; cin >> x >> y>>z; edges[x][y] = edges[y][x] = z; } cin >> q; int now = 0; for (int s = 0; s < q; s++) { int xx, yy, tt; cin >> xx >> yy >> tt; while (tt >=t[now] && now < n) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (edges[i][j] > edges[i][now] + edges[now][j]) edges[i][j]= edges[j][i] = edges[i][now] + edges[now][j]; now++; } if (t[xx] > tt || t[yy] > tt)cout << -1 << endl; else { if (edges[xx][yy] == INF)cout << -1<<endl; else cout << edges[xx][yy] << endl; } } }
原文：https://www.cnblogs.com/Jason66661010/p/12898845.html