题意：
有 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; else mp[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; }
