2020ICPC 江西省赛 K. Travel Expense(最短路+二分)

Description
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 2 1 2^1 21 and the fee of road 2->3 will be 2 2 2^2 22. So the total expense is 2 1 + 2 2 = 6 2^1+2^2=6 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.

Input
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.

Ouput
For each query, print one integer as the maximum item Huanhuan can carry from city S to T.

输入

3 2
1 2
2 3
3
1 2 5
1 3 5
2 3 2

输出

5
1
2

Solution
Floyd预处理任意两点最短距离后二分答案

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e2 + 10;
typedef long long ll;
const int inf=1e9+10;

int n,m,d[maxn][maxn];
inline bool check(int x, int len, int lim) {
	if(len == inf) return false;
	if(x==1) return len <= lim;
	ll sum = 0, p = x;
	for(int i = 0;i < len;++i) {
		sum += p;
		if(sum > 1ll*lim) return false;
		p*=1ll*x;
	}return sum <= 1ll*lim;
}
int solve(int s,int t,int lim) {
	int len = d[s][t];
	int l = 0, r = 1e9, mid, ans = 0;
	while(l <= r) {
		mid = (l + r) >> 1;
		if(check(mid,len,lim)) {ans = mid;l = mid + 1;}
		else r = mid - 1;
	}return ans;
}
int main(int argc, char const *argv[])
{
	scanf("%d%d",&n,&m);
	// memset(d,0x3f,sizeof(d));
	for(int i = 1;i <= n;++i) for(int j = 1;j <= n;++j) d[i][j] = inf;
	for(int i = 1;i <= m;++i) {
		int u,v;scanf("%d %d",&u,&v);
		d[u][v] = min(d[u][v],1);
		d[v][u] = d[u][v];
	}
	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]);
	int q;scanf("%d",&q);
	while(q--) {
		int s,t,lim;scanf("%d %d %d",&s,&t,&lim);
		//debug3(s,t,d[s][t]);
		int res = solve(s,t,lim);printf("%d\n", res);
	}
	return 0;
}