《P1462 通往奥格瑞玛的道路》
题目背景
在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量。
有一天他醒来后发现自己居然到了联盟的主城暴风城。
在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛。
题目描述
在艾泽拉斯，有 n 个城市。编号为 1,2,3,…,n。
城市之间有 m 条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。
每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。
假设 1 为暴风城，n 为奥格瑞玛，而他的血量最多为 b，出发时他的血量是满的。如果他的血量降低至负数，则他就无法到达奥格瑞玛。
歪嘴哦不希望花很多钱，他想知道，在所有可以到达奥格瑞玛的道路中，对于每条道路所经过的城市收费的最大值，最小值为多少。
输入格式
第一行 3 个正整数，n,m,b。分别表示有 n 个城市，m 条公路，歪嘴哦的血量为 b。
接下来有 n 行，每行 1 个正整数，fi。表示经过城市 i，需要交费 fi 元。
再接下来有 m 行，每行 3 个正整数，ai,bi,ci（1≤ai,bi≤n）。表示城市 ai 和城市 bi 之间有一条公路，如果从城市 ai 到城市 bi，或者从城市 bi 到城市 ai，会损失 ci 的血量。
输出格式
仅一个整数，表示歪嘴哦经过城市单次交费最大值的最小值。
如果他无法到达奥格瑞玛，输出 AFK。
输入输出样例
输入 #1复制
4 4 8 8 5 6 10 2 1 2 2 4 1 1 3 4 3 4 3
输出 #1复制
10
说明/提示
对于 60% 的数据，满足 n≤200，m≤104，b≤200；
对于 100% 的数据，满足 1≤n≤104，1≤m≤5×104，1≤b≤109；
对于 100% 的数据，满足 1≤ci≤109，0≤fi≤109，可能有两条边连接着相同的城市。
代码实现：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define MAXN 6666666
#define INF 9999999999
using namespace std;
// 快速读取整数
inline long long read_num(){
char ch='*';
while(!isdigit(ch=getchar()));
long long num=ch-'0';
while(isdigit(ch=getchar())) num=num*10+ch-'0';
return num;
}
// 图的邻接表表示
long long head[MAXN]; // 头节点数组
long long dest[MAXN]; // 目标节点
long long next_edge[MAXN]; // 下一条边
long long blood_cost[MAXN];// 边的血量消耗
long long edge_count; // 边计数器
// 添加边
inline void add_edge(long long from, long long to, long long cost){
dest[++edge_count] = to;
blood_cost[edge_count] = cost;
next_edge[edge_count] = head[from];
head[from] = edge_count;
}
// 全局变量
long long dist[MAXN]; // 到各节点的最小血量消耗
long long city_fee[MAXN]; // 各城市的过路费
long long city_count; // 城市数量
long long road_count; // 道路数量
long long max_blood; // 最大血量
bool in_queue[MAXN]; // 标记节点是否在队列中
// SPFA算法：计算在最大收费限制下的最小血量消耗
inline void spfa(int max_fee_limit){
memset(in_queue, 0, sizeof(in_queue));
for(int i = 1; i <= city_count; i++){
dist[i] = INF;
}
queue<int> q;
dist[1] = 0;
in_queue[1] = true;
q.push(1);
while(!q.empty()){
int current = q.front();
q.pop();
in_queue[current] = false;
for(int e = head[current]; e; e = next_edge[e]){
// 只允许通过收费不超过限制的城市
if(city_fee[dest[e]] <= max_fee_limit && dist[dest[e]] > dist[current] + blood_cost[e]){
dist[dest[e]] = dist[current] + blood_cost[e];
if(!in_queue[dest[e]]){
in_queue[dest[e]] = true;
q.push(dest[e]);
}
}
}
}
}
// 判断当前最大收费限制是否可行
inline bool is_possible(int mid_limit){
spfa(mid_limit);
if(dist[city_count] > max_blood) return false;
return true;
}
int main(){
long long left = 0, right = 0;
cin >> city_count >> road_count >> max_blood;
// 读取城市收费并确定二分查找范围
for(int i = 1; i <= city_count; i++){
cin >> city_fee[i];
right = max(right, city_fee[i]);
}
// 起点和终点的收费必须包含在范围内
left = max(city_fee[1], city_fee[city_count]);
// 读取道路信息
for(long long i = 1, u, v, cost; i <= road_count; i++){
cin >> u >> v >> cost;
add_edge(u, v, cost);
add_edge(v, u, cost);
}
// 初步检查是否存在可行路径
spfa(right);
if(dist[city_count] == INF || dist[city_count] > max_blood){
printf("AFK");
return 0;
}
// 二分查找最小的最大收费限制
while(left <= right){
int mid = (left + right) >> 1;
if(is_possible(mid)){
right = mid - 1;
} else {
left = mid + 1;
}
}
printf("%d", left);
return 0;
}