通往奥格瑞玛的道路
题目背景
在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量。
有一天他醒来后发现自己居然到了联盟的主城暴风城。
在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛。
题目描述
在艾泽拉斯，有 \(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\%\) 的数据，满足 \(n\leq 10^4\)，\(m\leq 5\times 10^4\)，\(b\leq 10^9\)；
对于 \(100\%\) 的数据，满足 \(c_i\leq 10^9\)，\(f_i\leq 10^9\)，可能有两条边连接着相同的城市。
分析
-
法1：既然要求最大费用的最小值，考虑把所有最大费用找出来，求最小，dfs/bfs，可能TLE。
-
法2：二分答案，spfa或者dijkstra求最短路，检查费用不超过mid的情况下能否到 n。
-
bfs，这个程序很奇怪呀，按理会TLE，但是没有，反而WA了，待调
-
spfa/pri_dijkstr，wa一个点，奇怪
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10,INF=0x3f3f3f3f;
int n,m,b,f[N],head[N],cnt=0,mx[N],pmx=0,vis[N],ans=INF;
struct T {
int to,nxt; LL w;
T(int a=0,LL b=0,int c=0):to(a),w(b),nxt(c) {}
bool operator< (const T& rhs) const {
return w > rhs.w;
}
} G[N], p;
void add(int u,int v,int w) {
G[++cnt].to=v;
G[cnt].w=w, G[cnt].nxt=head[u];
head[u]=cnt;
}
void bfs() {// 1->n 预计 TLE，无需 LL
queue<T> que;
que.push(T(1, b, f[1])), vis[1]=1;
while(que.size()) {
p = que.front(), que.pop();
if(p.to==n) {
ans=min(ans,p.nxt); continue;
}
int u=p.to, v, w, mf; vis[u]=1;
for(int i=head[u]; ~i; i=G[i].nxt) {
v=G[i].to, w=G[i].w, mf=max(f[v], p.nxt);
if(p.w >= w && !vis[v]) {
que.push(T(v,p.w-w,mf));
}
}
}
}
LL dis[N];
// 最大费用不超过mid的情况下能否到 n
bool spfa(int mid) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0x00, sizeof(vis));
queue<int> que;
que.push(1), dis[1]=0, vis[1]=1;
while(que.size()) {
int u=que.front(); que.pop(), vis[u]=0;
for(int i=head[u]; ~i; i=G[i].nxt) {
int v=G[i].to, w=G[i].w;
if(dis[v] > dis[u]+w && f[v]<=mid) {
dis[v] = dis[u]+w;
if(!vis[v]) que.push(v), vis[v]=1;
}
}
}
return dis[n]<=b;
}
bool pri_dijkstra(int mid) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0x00, sizeof(vis));
priority_queue<T> que;
que.push(T(1,0)), dis[1]=0;
while(que.size()) {
int u=que.top().to; que.pop();
if(vis[u]) continue; vis[u]=1;
for(int i=head[u]; ~i; i=G[i].nxt) {
LL v=G[i].to, w=G[i].w;
if(dis[v] > dis[u]+w && f[v]<=mid) {
dis[v] = dis[u]+w;
que.push(T(v,dis[v]));
}
}
}
return dis[n]<=b;
}
int main() {
freopen("data.in", "r", stdin);
memset(head,-1,sizeof(head));
scanf("%d%d%d", &n,&m,&b);
for(int i=1; i<=n; i++) scanf("%d", &f[i]);
int u,v,w;
for(int i=1; i<=m; i++) {
scanf("%d%d%d",&u,&v,&w), add(u,v,w), add(v,u,w);
}
// bfs();
int l=1, r=-1;
for(int i=1; i<=n; i++) r=max(r,f[i]);
while(l<=r) {
int mid=(l+r)/2;
if(spfa(mid)) ans=mid,r=mid-1;
// if(pri_dijkstra(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
if(ans==INF) printf("AFK\n");
else printf("%d\n",ans);
return 0;
}