笔者太菜直到现在才开始看最短路加二分……
解：
显然题目要二分，因为根据多年的经验，看到最大值最小，二话不说想二分……
既然问的是收费情况，那我们不妨二分收费情况。
题目都让我们输入交费数组了，不用它用谁呢？
l=1，r=n，开始二分。注意，左右边界是数组下标。
二分前，注意排序，sort一遍即可。同时，这意味着我们需要另一个数组来copy一下原数组。
依次判断中间值，缩小区间。如果当前交费比起点或终点还少的话，绝对不是答案，return false;
继续判断，将这个点的收费大与当前二分的收费的点的vis全部设为已经访问。
前向星存边，，边权就是生命值。
跑一遍堆优化dijkstra即可。
最后，再来判断，当前的最短路值（即所需生命）是否符合要求？符合，则True,不符合，则False.
注意，我们二分的是下标，所以，最后的答案应该是C[l],或者另开一个变量记录好了。（每个人的二分方法不一样，不一定是C[l]）
Code:
#include<cstdio> #include<iostream> #include<queue> #include<algorithm> #include<cstring> #define inf 2147483647 #define int long long using namespace std; int n,m,hp,vis[500000],tot,ans; int dis[500000],head[500000]; int w[500000],c[500000],l,r; struct edge{ int next,to,dis; }e[500000]; inline void add(int x,int y,int z){ e[++tot].next=head[x]; e[tot].to=y; e[tot].dis=z; head[x]=tot; } struct node{ int dis,pos; bool operator <(const node&x)const{ return x.dis<dis; } }; priority_queue<node>q; bool check(int Nhp){//二分当前money if(w[1]>Nhp||w[n]>Nhp)return false; //priority_queue<node>q; for(int i=1;i<=n;++i)dis[i]=inf; for(int i=1;i<=n;++i) if(w[i]>Nhp)vis[i]=true;//要钱太多不走 else vis[i]=false; dis[1]=0;q.push((node){0,1});//dijkstra while(!q.empty()){ node tmp=q.top(); q.pop(); int x=tmp.pos; if(vis[x])continue; vis[x]=true; for(int i=head[x];i;i=e[i].next){ int y=e[i].to; if(dis[y]>dis[x]+e[i].dis){ dis[y]=dis[x]+e[i].dis; if(!vis[y])q.push((node){dis[y],y}); } } }if(dis[n]<=hp)return true;//有命走到 else return false;//没命走到 } signed main(){ scanf("%lld%lld%lld",&n,&m,&hp); for(int i=1;i<=n;++i)scanf("%lld",&w[i]),c[i]=w[i]; for(int i=1;i<=m;++i){ int a,b,c; scanf("%lld%lld%lld",&a,&b,&c); if(a==b)continue; add(a,b,c);add(b,a,c); }sort(c+1,c+n+1); l=1,r=n; if(!check(c[n])){ printf("AFK ");i return 0; }ans=c[n]; while(l<=r){ int mid=l+r>>1; if(check(c[mid]))r=mid-1,ans=c[mid]; else l=mid+1; }printf("%lld ",ans); return 0; }