洛谷p1462-通往奥格瑞码道路

题目：https://www.luogu.com.cn/problem/P1462
思考过程：
刚拿到这个题，我把消耗的血量和路费当成了负权边去考虑，考虑到我们只需要考虑扣钱的最优，并且在血量扣尽之前达到就好，那我觉得可以用一个数组hp来代表实时血量，拿一个值来更新目前到这个点的最大花费，我觉得肯定是优先走钱少的点，如果hp被扣完了，再回溯走下一个。
如果按我这个思路走就是dij+spfa+贪心+dfs，就特别麻烦，后来看题解思路意识到，“最大的最小，最小的最大”之类的题，用二分。
那么这道题就可以用二分加dij简易实现。用二分查找一个值，这个值要介于f数组最小和最大之间才能构成二分。然后判断是否存在这么一条路，如果能在hp减为0之前能达到，说明这个mid值是ok的，就可以继续降低mid值，反之增大。
接下来是代码实现：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll INF=1e18;
bool check(ll mid,int n,int b,const vector<int>&ff,const vector<vector<pair<int,int>>>&gg){if(ff[1]>mid||ff[n]>mid) return false;vector<ll>dist(n+1,INF);vector<bool>vis(n+1,false);priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;pq.push({0,1});dist[1]=0;// vis[1]=true;while(!pq.empty()){auto[d,u]=pq.top();pq.pop();if(vis[u]) continue;vis[u]=true;for(auto[v,w]:gg[u]){if(ff[v]<=mid){if(d+w<dist[v]){dist[v]=d+w;pq.push({dist[v],v});}}}}return dist[n]<=b;
}
void solve(){int n,m;ll b;cin>>n>>m>>b;vector<int>f(n+1);int maxf=0;for(int i=1;i<=n;i++){// int f;cin>>f[i];maxf=max(maxf,f[i]);}vector<vector<pair<int,int>>>g(n+1);for(int i=0;i<m;i++){int u,v,w;cin>>u>>v>>w;g[u].push_back({v,w});g[v].push_back({u,w});}ll l=0;ll r=ll(maxf)+1;ll ans=-1;while(l<=r){ll mid=(l+r)>>1;if(check(mid,n,b,f,g)){ans=mid;r=mid-1;}else l=mid+1;}if(ans==-1) cout<<"AFK\n";else cout<<ans<<"\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);solve();return 0;
}