526互联

【LuoGU 1462】通往奥格瑞玛的道路——最短路+二分

发布时间 2023-08-05 17:00:04作者: 天涯海角寻天涯

通往奥格瑞玛的道路

题目背景

在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量。

有一天他醒来后发现自己居然到了联盟的主城暴风城。

在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛。

题目描述

在艾泽拉斯，有 \(n\) 个城市。编号为 \(1,2,3,\ldots,n\)。

城市之间有 \(m\) 条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。

每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。

假设 \(1\) 为暴风城，\(n\) 为奥格瑞玛，而他的血量最多为 \(b\)，出发时他的血量是满的。如果他的血量降低至负数，则他就无法到达奥格瑞玛。

歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。

输入格式

第一行 \(3\) 个正整数，\(n,m,b\)。分别表示有 \(n\) 个城市，\(m\) 条公路，歪嘴哦的血量为 \(b\)。

接下来有 \(n\) 行，每行 \(1\) 个正整数，\(f_i\)。表示经过城市 \(i\)，需要交费 \(f_i\) 元。

再接下来有 \(m\) 行，每行 \(3\) 个正整数，\(a_i,b_i,c_i\)（\(1\leq a_i,b_i\leq n\)）。表示城市 \(a_i\) 和城市 \(b_i\) 之间有一条公路，如果从城市 \(a_i\) 到城市 \(b_i\)，或者从城市 \(b_i\) 到城市 \(a_i\)，会损失 \(c_i\) 的血量。

输出格式

仅一个整数，表示歪嘴哦交费最多的一次的最小值。

如果他无法到达奥格瑞玛，输出 AFK。

样例 #1

样例输入 #1

4 4 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3

样例输出 #1

10

提示

对于 \(60\%\) 的数据，满足 \(n\leq 200\)，\(m\leq 10^4\)，\(b\leq 200\)；

对于 \(100\%\) 的数据，满足 \(1\leq n\leq 10^4\)，\(1\leq m\leq 5\times 10^4\)，\(1\leq b\leq 10^9\)；

对于 \(100\%\) 的数据，满足 \(1\leq c_i\leq 10^9\)，\(1\leq f_i\leq 10^9\)，可能有两条边连接着相同的城市。

解法

二分 + Dijkstra最短路

个人感觉本题的一个难点在于读题：题目问的是经过的所有城市中//最多的一次收取的费用//的最小值。也就是要我们求在歪嘴哦经过的所有路径中，收过路费收的最多的这个城市收的过路费的最小值。也就是将一个城市收取的过路费的最大值最小化。
察觉到关键词，于是就要往二分上靠。不难发现答案具有二段性：每个城市收的过路费的最大值越小，能走的路径就越少，能到达终点的可能性也越小。
然后题目中还有一个血量限制，这里就可以用到最短路了: 将血量消耗看成是边权，每二分出一个\(x\)后跑一遍Dijkstra，如果最短路的消耗都大于\(b\)则返回\(false\)，否则返回\(true\)。
注意细节:
\(1、\)判断不可达：所有路径都能走的情况下最短路径的消耗依然大于\(b\)，则歪嘴哦无法到达奥格瑞玛。
\(2、\)如果起点的过路费已经大于二分枚举出来的\(x\)，则直接判断为假。该种情况需要特判！

#include<bits/stdc++.h>

typedef long long ll;

typedef std::pair<ll, ll> pll;

const int N = 100010;

int n, m, b;
std::vector<std::vector<pll>> g(N);
int f[N];
int maxf;
int blood;
bool flag;

bool dijkstra(int x) {
	std::vector<long long> dist(n + 1, LLONG_MAX);
	dist[1] = 0;

	std::priority_queue<pll, std::vector<pll>, std::greater<pll>> pq;
	pq.push({0, 1});

	while(!pq.empty()) {
		auto hh = pq.top();
		pq.pop();

		long long d = hh.first;
		int u = hh.second;
		if(d > dist[u]) continue;

		for(auto tt: g[u]){
			int v = tt.first, c = tt.second;
			if(f[v] > x) continue;
			long long new_d = d + (long long)c;
			if(new_d < dist[v]) {
				dist[v] = new_d;
				pq.push({dist[v], v});
			}
		}
	}
	return dist[n] <= b;
}

bool check(int x) {
	return dijkstra(x);
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);

	std::cin >> n >> m >> b;
	for(int i = 1; i <= n; i ++ ){
		std::cin >> f[i];
		maxf = std::max(f[i], maxf);
	}

	for(int i = 0; i < m; i ++ ){
		int a, b, c;
		std::cin >> a >> b >> c;
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}

	int l = 1, r = maxf;
	if(!check(r)) {
		std::cout << "AFK" << '\n';
		return 0;
	}
	while(l < r) {
		int mid = l + r >> 1;
		if(f[1] <= mid && check(mid)) r = mid;
		else l = mid + 1;
	}
	std::cout << r << '\n';
	return 0;
}