NC213992. TravelExpense
描述
Huanhuan is always working on fansy programming questions. However, today he decided to give himself a break and travel to a beautiful country. Therefore, another problem arose.
There are totally n cities in the country. There are m two-way roads, each of them directly connects two different cities. As the country has a solid transportation system, there is always a path connects every two cities.
Huanhuan arrives at city S and wants to carry as many items as possible to city T. Everyday he will go through exactly one road. For every road he pass, a fee is to pay. Due to the policy, the fee depends on number of items you carry and the number of days you enter the country. More exactly, the fee for each road is kd, where k is the number of the items Huanghuan is to carry and d is the number of days he enter the country.
For example , Huanghuan arrives ar city 1 , and aim to city 3. The path he chooses is 1->2->3 carrying 2 items . Then the fee of road 1->2 will be 21 and the fee of road 2->3 will be 22. So the total expense is 21+22=6
Now, you are tasked to help him to decide the maximum number of items he can carry since he only have limited budget.
However, Huanhuan is prepared to travel multiple times in the future. There will be totally Q query for you.
输入描述
Thefirst line contains two interger n,m (1≤n≤100, m≤(n(n+1)/2)),where n is number of cities and m is the number of road. (It's guaranteed that every two cities are connected, and there are no two roads directly connects the same two cities.)Then, m lines follow, the ith lines contains two integer ui, vi (1≤ui, vi≤n, ui≠vi), denoting the ith roads connects city ui and vi.The next lines contains one integer Q (1≤Q≤105), denoting the number of query.Then follows Q lines, each line contains 3 integers S, T, B (1≤S, T≤n, 0≤B≤109), denoting the city arrived, the city aimed and the budget.
输出描述
For each query, print one integer as the maximum item Huanhuan can carry from city S to T.
示例1
输入:
3 2 1 2 2 3 3 1 2 5 1 3 5 2 3 2
输出:
5 1 2
C++ 解法, 执行用时: 285ms, 内存消耗: 928K, 提交时间: 2022-06-28 19:37:05
#include<bits/stdc++.h>
#define N 105
using namespace std;
int n,m,a,b,c,dp[N][N];
int main()
{
cin>>n>>m;
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=m;i++)
{
cin>>a>>b;
dp[a][b]=dp[b][a]=1;
}
for(int i=1;i<=n;i++) dp[i][i]=0;
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
cin>>m;
while(m)
{
m--;
cin>>a>>b>>c;
long long l=0,r=pow(c,1.0/dp[a][b]),mid;
while(l<r)
{
mid=(l+r+1)/2;
long long ans;
if(mid==1) ans=dp[a][b];
else ans=(long long)mid*(pow(mid,dp[a][b])-1)/(mid-1);
if(ans<=c) l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
return 0;
}