问题 E: Travel by Car
题目描述
There are N towns numbered 1 to N and M roads. The i-th road connects Town Ai and Town Bi bidirectionally and has a length of Ci.
Takahashi will travel between these towns by car, passing through these roads. The fuel tank of his car can contain at most L liters of fuel, and one liter of fuel is consumed for each unit distance traveled. When visiting a town while traveling, he can full the tank (or choose not to do so). Travel that results in the tank becoming empty halfway on the road cannot be done.
Process the following Q queries:
The tank is now full. Find the minimum number of times he needs to full his tank while traveling from Town si to Town ti. If Town ti is unreachable, print −1.
Constraints
·All values in input are integers.
·2≤N≤300
·0≤M≤N(N−1)/2
·1≤L≤109
·1≤Ai,Bi≤N
·Ai≠Bi
·(Ai,Bi)≠(Aj,Bj) (if i≠j)
·(Ai,Bi)≠(Bj,Aj) (if i≠j)
·1≤Ci≤109
·1≤Q≤N(N−1)
·1≤si,ti≤N
·si≠ti
·(si,ti)≠(sj,tj) (if i≠j)
输入
Input is given from Standard Input in the following format:
N M L
A1 B1 C1
:
AM BM CM
Q
s1 t1
:
sQ tQ
输出
Print Q lines.
The i-th line should contain the minimum number of times the tank needs to be fulled while traveling from Town si to Town ti. If Town ti is unreachable, the line should contain −1 instead.
样例输入 Copy
【样例1】
3 2 5
1 2 3
2 3 3
2
3 2
1 3
【样例2】
4 0 1
1
2 1
【样例3】
5 4 4
1 2 2
2 3 2
3 4 3
4 5 2
20
2 1
3 1
4 1
5 1
1 2
3 2
4 2
5 2
1 3
2 3
4 3
5 3
1 4
2 4
3 4
5 4
1 5
2 5
3 5
4 5
样例输出 Copy
【样例1】
0
1
【样例2】
-1
【样例3】
0
0
1
2
0
0
1
2
0
0
0
1
1
1
0
0
2
2
1
0
提示
样例1解释
To travel from Town 3 to Town 2, we can use the second road to reach Town 2 without fueling the tank on the way.
To travel from Town 1 to Town 3, we can first use the first road to get to Town 2, full the tank, and use the second road to reach Town 3.
样例2解释
There may be no road at all.
题意： N个点，M条双向道路，在行驶过程中车会耗油。在经过每个点时可以选择加满油或不加油，给出q次询问，问汽车从s到e点的最少加油量。
思路： 最短路~显而易见。
所以最开始写了个求最短距离的最短路，对每次结果除以油箱油量。其实仔细想想这种思路是错的，因为加油是只能在每一个点加，而不是在任意点都能加。
看一下正确的思路，先对题目中给定的图进行计算，算出每两个点之间的距离，再根据这个距离建新的图。我们设d [i] [j] 表示从 i 到 j 的最短路径，如果这个值小于油箱容量就说明这两个点不需要加油就可以到达，反之说明必须要加油才能到达。我们在这个基础上再跑一遍Floyd 就可以得出答案了。
最后需要注意答案输出时要-1，因为我们假设车子一开始是没有油的，而题目中车子一开始是满油的。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define I_int ll inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } const int maxn=310,mod=1e9+7; const ll inf=1e13; ll d[maxn][maxn],cnt[maxn][maxn]; ll n,m,l,q,s,t; void AC(){ n=read();m=read();l=read(); ll a,b,c; for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++) if(i==j) d[i][j]=0; else d[i][j]=inf; for(int i=1;i<=m;i++){ a=read();b=read();c=read(); if(c<=l&&c<d[a][b]) d[a][b]=d[b][a]=c; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) 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(i==j) continue; else{ if(d[i][j]<=l) cnt[i][j]=1; else cnt[i][j]=inf; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cnt[i][j]=min(cnt[i][j],cnt[i][k]+cnt[k][j]); q=read(); while(q--){ s=read();t=read(); if(cnt[s][t]==inf) cout<<"-1"; else out(cnt[s][t]-1); puts(""); } //out(res); } int main(){ AC(); return 0; }
