Travel Expense

给出一张图，多次询问点a到b的最大携带货物量i为多少，假设a到b距离为k,则花费金额为i^1+i^2...i^k，要求是花费不能大于上限b。
首先最短路是显然的。注意到地图的数据范围n,m (1≤n≤100, m≤(n(n+1)/2))，查询次数Q (1≤Q≤10^5),地图范围很小而需要频繁的询问不同点之间的距离，显然是floyd。至于寻找最大携带货物量用二分查找即可。
注意，判断上式是否大于b，如果用我这种写法需要在大于b的时候及时return false,否则会爆数据范围。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=110;
const ll inf=0x3f3f3f;
int mp[maxn][maxn];
int n, m, q;
void floyd(int n)
{
    for (int k = 1; k <= n;k++)
    for(int i = 1;i <= n;i++)
    for (int j = 1; j <= n;j++)
        if(mp[i][j] > mp[i][k] + mp[k][j])
        {
            mp[i][j] = mp[i][k] + mp[k][j];
        }
}
ll quick_pow(int a,int b)
{
    ll ans = 1,base = a;
    while(b)
    {
        if(b&1)
            ans = ans * base;
        base = base * base;
        b >>= 1;
    }
    return ans;
}
bool work(int num,int len,ll up)
{
    ll ans = 0;
    for(int i = 1;i <= len;i++)
    {
        ans += quick_pow(num,i);
        if(ans > up)
            return false;
    }
    return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(mp,inf,sizeof(mp));
    for (int i = 1;i <= m;i++)
    {
        int u,v;
        scanf("%d%d", &u, &v);
        mp[u][v] = mp[v][u] = 1;
    }
    floyd(n);
    scanf("%d", &q);
    for(int i = 1;i <= q;i++)
    {
        int u,v,up;
        scanf("%d%d%d", &u, &v, &up);
        int l = 1, r = up+1;
        int len = mp[u][v];
        int ans;
        while(l < r)
        {
            int mid = (l + r)/2;
            if(work(mid,len,up))
                l = mid + 1;
            else
                r = mid;
        }
        cout << l-1 << endl;
    }
    return 0;
}
/*
5 4
1 2
2 3
3 4
3 5
4
1 5 15
1 5 13
1 3 7
1 3 5
*/