\(n\le300\)
可凭感觉进行一遍 Floyd。
然后选两个点 \(i,j\)，如果 \(i,j\) 间的距离小于等于 \(l\)，则将 \(i,j\) 连一条代价为 \(1\) 的边（假设 \(i,j\) 要用一桶油）。
最后再来一遍 Floyd 即可。
因为第一次是加满油的，所以答案要 \(-1\)。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=305;
int n,m,l,q,s,t,u,v,w;
int d[N][N],dis[N][N];
signed main() {
cin>>n>>m>>l;
for(int i=0;i<=n;++i) {
fill(d[i],d[i]+N,1e16);
fill(dis[i],dis[i]+N,1e16);
d[i][i]=dis[i][i]=0;
}
for(int i=1;i<=m;++i) {
cin>>u>>v>>w;
d[u][v]=d[v][u]=w;
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(d[i][k]!=1e16&&d[k][j]!=1e16)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(d[i][j]<=l) dis[i][j]=dis[j][i]=1;
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(dis[i][k]!=1e16&&dis[k][j]!=1e16)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
cin>>q;
while(q--) {
cin>>u>>v;
cout<<(dis[u][v]!=1e16?dis[u][v]-1:-1)<<endl;
}
return 0;
}