29 lines
1.0 KiB
C++
29 lines
1.0 KiB
C++
// P1119 灾后重建。原题编号 0..n-1，重建时间和询问时间分别不下降。
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
using ll = long long;
|
|
int main() {
|
|
ios::sync_with_stdio(false); cin.tie(nullptr);
|
|
int n, m; if (!(cin >> n >> m)) return 0;
|
|
vector<int> repair(n); for (int &t : repair) cin >> t;
|
|
const ll INF = 1LL << 60;
|
|
vector<vector<ll>> d(n, vector<ll>(n, INF));
|
|
for (int i = 0; i < n; ++i) d[i][i] = 0;
|
|
for (int e = 0, u, v; e < m; ++e) {
|
|
ll w; cin >> u >> v >> w; d[u][v] = d[v][u] = min(d[u][v],w);
|
|
}
|
|
int Q, k = 0; cin >> Q;
|
|
while (Q--) {
|
|
int x, y, t; cin >> x >> y >> t;
|
|
while (k < n && repair[k] <= t) {
|
|
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
|
|
if (d[i][k] == INF || d[k][j] == INF) continue;
|
|
d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
|
|
}
|
|
++k;
|
|
}
|
|
if (repair[x] > t || repair[y] > t || d[x][y] == INF) cout << -1 << '\n';
|
|
else cout << d[x][y] << '\n';
|
|
}
|
|
}
|