P1119 灾后重建

点击查看代码

#include<bits/stdc++.h>
using namespace std;const int MAXN = 205;
const int INF = 1e9; // 定义一个足够大的数代表无穷大int n, m;
int t[MAXN];          //存每个村庄的修复时间
int dist[MAXN][MAXN]; int main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 0; i < n; i++) {cin >> t[i];}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j) dist[i][j] = 0;else dist[i][j] = INF;}}for (int i = 0; i < m; i++) {int u, v, w;cin >> u >> v >> w;dist[u][v] = dist[v][u] = w; }int q;cin >> q;int now = 0; //记录当前floyd解锁到了哪个村庄了while (q--) {int x, y, time;cin >> x >> y >> time;//按时间决定要遍历作为中转点的村庄数量，这样相当于只跑了now层，等程序结束也才跑了一个三重循环while (now < n && t[now] <= time) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (dist[i][now] != INF && dist[now][j] != INF) {dist[i][j] = min(dist[i][j], dist[i][now] + dist[now][j]);}}}now++; }//没修好不可达，不连通不可达if (t[x] > time || t[y] > time || dist[x][y] == INF) {cout << -1 << endl;} else {cout << dist[x][y] << endl;}}return 0;
}