原题链接

Floyd离线路径探索初体验

本题需要两次Floyd算法。
第一次是对给定的图进行计算，求出G[i][j]，来表示村子i到村子j的最小路径长度。
然后把G[i][j]转换成或的图。（若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];
 

    //Floyd
    REP1(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;
    
    //Floyd
    REP1(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;
}