题目传送:链接
思路
算法:\(Floyd.\)
- 每次询问记录一个变量 \(n\),表示当前遍历到哪个点。
- 当 \(t_n <= T\) 的时候,利用 \(n\) 点更新到 $(x,y) $ 点的最短路。
- 如果发现 \(x,y\) 点其中有一个还没有修好,或者是 \(d_{x_y}\) 为
0x3f3f3f3f
,就输出 \(-1\) 。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int t[N], d[N][N];
int n, m, q, Time, x, y, len, now;
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%d", &t[i]);
d[i][i] = 0; // 自己到自己的最短路为0
}
memset(d, 0x3f, sizeof(d)); // 初始化
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &x, &y, &len);
d[x][y] = d[y][x] = len;
}
scanf("%d", &q);
while (q--) { // q次询问
scanf("%d%d%d", &x, &y, &Time);
while (t[now] <= Time && now < n) { // 之前的点修好了,就用这个点更新最短路
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
d[i][j] = min(d[i][j], d[i][now] + d[now][j]);
}
}
now++; // 点的编号自增
}
if (d[x][y] == INF || t[x] > Time || t[y] > Time) printf("-1\n"); // 走不到
else printf("%d\n", d[x][y]);
}
return 0;
}
标签:int,P1119,scanf,Time,灾后,printf,0x3f3f3f3f,重建
From: https://www.cnblogs.com/yhx0322/p/17739247.html