题意分析
求经过的城市收费最大值的最小值，显然需要二分答案。
那么二分这个值，之后只需要跑一遍最短路即可。
注意不要混淆“血量”与城市“收费”即可。
AC 代码
时间复杂度：$\mathcal O((n+m)\log m\log n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=1e4,M=5e4;
int n,m,b,f[N+1];
vector<pair<int,int> >g[N+1];
//f[i]<=mid
bool check(int mid){
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
static ll dis[N+1];
static bool vis[N+1];
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[1]=0;
q.push({dis[1],1});
while(q.size()){
int x=q.top().second;q.pop();
if(vis[x]){
continue;
}
for(auto &i:g[x]){
int &v=i.first,&w=i.second;
if(vis[v]||f[v]>mid){
continue;
}
if(dis[x]+w<dis[v]){
dis[v]=dis[x]+w;
q.push({dis[v],v});
}
}
}
return dis[n]<=b;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>b;
int l=2147483647,r=0;
for(int i=1;i<=n;i++){
cin>>f[i];
l=min(l,f[i]);
r=max(r,f[i]);
}
while(m--){
int u,v,w;
cin>>u>>v>>w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
int ans=2147483647;
l=max({l,f[1],f[n]});
while(l<=r){
int mid=l+r>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
if(ans==2147483647){
cout<<"AFK\n";
}else{
cout<<ans<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
