本文主要是介绍2020ICPC 江西省大学生程序设计竞赛 K.Travel Expense，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
有 n 座城市，m 条双向道路，一条道路要走一天，每条道路的费用是 items ^ days （ items 是所携带的物品数量， days 是第几天），现在查询q次，（1-1e5）然后给你一个出发城市 S ，目的地城市 T ，预算 B ，问最多能携带多少物品。
思路：
Floyd预处理每个点之间的最短路，因为长度不大所以可以跑，n^3的复杂度，然后接下来二分枚举答案，输出最优解，求幂次方可以用快速幂优化一下，不过这里要判断溢出和大于，不然容易爆longlong.
#include<bits/stdc++.h>using namespace std;const int maxn=105;
const int inf=0x3f3f3f3f3f;
#define int long long
int mp[maxn][maxn];
long long n,m,B;
long long quickpow(int a,int b)
{long long res=1;while(b!=0){if(b&1) res*=a;b>>=1;a*=a;}return res;
}
bool check(int mid,int x)
{long long dd=0;for(int d1=1;d1<=x;d1++){dd+=quickpow(mid,d1);if(dd>B||dd<0) {return false;}}if(dd>B) return false;return true;
}
signed main()
{int s,t,b,u,v,i,j,k,q;cin>>n>>m;for(i=0;i<maxn;i++){for(j=0;j<maxn;j++){if(i!=j)mp[i][j]=inf,mp[j][i]=inf;elsemp[i][j]=0;}}for(i=0;i<m;i++){cin>>u>>v;mp[u][v]=1;mp[v][u]=1;}cin>>q;for(k=1;k<=n;k++){for(i=1;i<=n;i++){for(j=1;j<=n;j++){mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);}}}for(i=0;i<q;i++){cin>>s>>t>>B;int l=0,r=1000000007;if(mp[s][t]==0||mp[s][t]==inf) {cout<<0<<endl;continue;}while(l<r){int mid=l+r+1>>1;if(check(mid,mp[s][t])){l=mid;}else{r=mid-1;}}cout<<l<<endl;}return 0;
}
这篇关于2020ICPC 江西省大学生程序设计竞赛 K.Travel Expense的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
