原题链接
Floyd离线路径探索初体验
本题需要两次Floyd算法。
第一次是对给定的图进行计算，求出G[i][j]，来表示村子i到村子j的最小路径长度。
然后把G[i][j]转换成 ∞ \infty ∞或 1 1 1的图。（若G[i][j]<=l则设为1，否则设为无穷大）
然后再对这个G进行第二次Floyd。
最后根据答案集输出答案即可（所有答案需要-1，结果本质上是假设了车子一开始没油，但题目假设是车子一开始满油）。
点击这里查看完整源码
#include<bits/stdc++.h>
using namespace std;
//省略一些宏
//---------------------
#define MAXN 305
#define INF 300000000900
//---------------------ll n,m,l,q;
ll s[MAXN*MAXN];
ll t[MAXN*MAXN];ll G[MAXN][MAXN];
ll F[MAXN][MAXN];int main(){
cin >> n >> m >> l;REP2D1(i,j,n,n) G[i][j] = INF;REP(i,m){
ll a,b,c;cin >> a >> b >> c;G[a][b] = G[b][a] = c;}REP1(i,n) G[i][i] = 0;cin >> q;REP(i,q) cin >> s[i] >> t[i];//FloydREP1(k,n) REP2D1(i,j,n,n)G[i][j] = min(G[i][j],G[i][k]+G[k][j]);REP2D1(i,j,n,n) if(G[i][j]<=l) F[i][j] = 1; else F[i][j] = INF;//FloydREP1(k,n) REP2D1(i,j,n,n)F[i][j] = min(F[i][j],F[i][k]+F[k][j]);REP(i,q) PRT(F[s[i]][t[i]]>=INF?-1:F[s[i]][t[i]]-1);return 0;
}