题意
简述一下题意。给定一张图，每条边是双向的。给定一个数\(b\)，求一个最小\(ans\)和一条从\(1\)到\(n\)的路径，使边权和\(<=b\)，点权最大值\(<=ans\)。
思路
看到求点权最大值最小，想到二分。又要让边权和最小，想到最短路。具体来讲，二分一个\(mid\)，对于每个\(mid\)，跑一边最短路（\(Dijkstra\)或\(SPFA\)）\(check\)一下，如果点权\(>mid\)或者边权\(>b\)就跳过这个点，最后看一下能不能到达终点，也就是\(dis_{n}\)有没有被更新过。时间复杂度\(O(m log m log 1e9)\)。
注意
\(1.\) 最后要判无解情况，输出\(AFK\)。
\(2.\) 二分下界要设为\(f_{1}\)，因为必须经过\(1\)号点。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
typedef pair <int,int> pii;
const int MAXN = 1e5 + 10;
int n,m,b,f[MAXN],x,y,z,head[MAXN],cnt,dis[MAXN],ans;
bool vis[MAXN];
struct Node
{
int u,v,w,nxt;
}e[MAXN << 1];
void add(int u,int v,int w){e[++cnt] = {u,v,w,head[u]};head[u] = cnt;}
priority_queue <pii,vector <pii>,greater <pii> > q;
void dijkstra(int N,int s,int maxn)
{
memset(vis,0,sizeof vis);
for(int i = 1;i <= n;i++) dis[i] = inf;
dis[s] = 0;
q.push(make_pair(N,s));
while(!q.empty())
{
int u = q.top().second;q.pop();
for(int i = head[u]; ~ i;i = e[i].nxt)
{
int now = e[i].v;
if(vis[now] == true || f[now] > maxn) continue;
if(dis[u] + e[i].w < dis[now] && dis[u] + e[i].w <= b)
{
dis[now] = dis[u] + e[i].w;
vis[now] = true;
q.push(make_pair(dis[now],now));
}
}
}
}
signed main()
{
memset(head,-1,sizeof head);
cin >> n >> m >> b;
for(int i = 1;i <= n;i++) cin >> f[i];
for(int i = 1;i <= m;i++) cin >> x >> y >> z,add(x,y,z),add(y,x,z);
int l = f[1],r = 1e15;
while(l <= r)
{
int mid = (l + r) >> 1;
dijkstra(0,1,mid);
if(dis[n] == inf) l = mid + 1;
else r = mid - 1,ans = mid;
}
if(ans == 0) cout << "AFK" << endl;
else cout << ans << endl;
return 0;
}