算法
(floyd) $O(n^3)$
我们不能仅仅以上面某种方式来考虑,而是应该往 从s点出发能走多远
这个角度来思考。
首先用 floyd
算法求出任意两点间的最短路 $dist[a][b]$
初始化:
$$ dist[a][b] = \begin{cases} \text{长度} \, , & \text{有边} \\\ \infty \, , & \text{无边} \\\ 0 \, , & a = b \end{cases} $$
转移方程:
$$ dist[i][j] = \min(dist[i][j], dist[i][k] + dist[k][j]) $$
其次注意到如果两点间的最短路 $dist[a][b] \leqslant L$ 则只需要加一次油就足够了
然后再次利用 floyd
算法来找到任意两点之间互达需要加多少次油,记为 $dist2[a][b]$。
又因为起点不需要加油,所以 ans = dist[s][t] - 1
。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
bool chmin(int& x, int y) { if (x > y) { x = y; return true; } return false; }
int main() {
int n, m, l;
cin >> n >> m >> l;
const int INF = 1001001001;
vector dist(n, vector<int>(n, INF));
rep(i, n) dist[i][i] = 0;
rep(i, m) {
int a, b, c;
cin >> a >> b >> c;
--a; --b;
dist[a][b] = dist[b][a] = c;
}
rep(k, n)rep(i, n)rep(j, n) chmin(dist[i][j], dist[i][k] + dist[k][j]);
vector dist2(n, vector<int>(n, INF));
rep(i, n)rep(j, n) {
if (dist[i][j] <= l) dist2[i][j] = 1;
}
rep(k, n)rep(i, n)rep(j, n) chmin(dist2[i][j], dist2[i][k] + dist2[k][j]);
int q;
cin >> q;
rep(qi, q) {
int s, t;
cin >> s >> t;
--s; --t;
int ans = dist2[s][t] - 1;
if (dist2[s][t] == INF) ans = -1;
cout << ans << '\n';
}
return 0;
}