【洛谷P1462】通往奥格瑞玛的道路【二分】【最短路】

本文主要是介绍【洛谷P1462】通往奥格瑞玛的道路【二分】【最短路】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P1462
给出一张无向图，每个点和边都有权值。求从 $1$ 到 $n$ 的所有路径中，在边权不超过 $b$ 的情况下点权的最大值最小。

思路：

这道题很明显是要二分答案的。因为要使最大的点权尽量小，所以就二分这个最大的点权 $m i d$ ，然后跑 $S P F A$ ，要求路径上的点的权值都不能超过 $m i d$ 。然后如果最终 $dis[n]\leq b$ ，那么就说明点权最大为mid的情况是合法的，然后继续二分即可。
$B F S$ 也可以过。感觉这道题目没有蓝题难度，毕竟一下就想出了正解。

代码：

#include <cstdio>
#include <cstring>
#include <queue>
#define N 10100
#define M 50100
#define Inf 1e9
#define ll long long
using namespace std;int cost[N],n,m,hp,head[N],tot,l,r,mid;
bool vis[N];
ll dis[N];struct edge
{int next,to;ll dis;
}e[M*2];void add(int from,int to,ll dis)
{e[++tot].to=to;e[tot].dis=dis;e[tot].next=head[from];head[from]=tot;
}bool spfa(int k)
{if (cost[1]>k) return 0;  //如果第一个点都直接超过了mid,那么肯定不行queue<int> q;for (int i=1;i<=n;i++){vis[i]=0;dis[i]=Inf;}q.push(1);vis[1]=1;dis[1]=0;while (q.size()){int u=q.front();q.pop();vis[u]=0;for (int i=head[u];~i;i=e[i].next){int v=e[i].to;if (cost[v]>k) continue;  //判断有没有超过midif (dis[v]>dis[u]+e[i].dis){dis[v]=dis[u]+e[i].dis;if (!vis[v]){q.push(v);vis[v]=1;}}}}return dis[n]<=hp;
}int main()
{memset(head,-1,sizeof(head));scanf("%d%d%d",&n,&m,&hp);for (int i=1;i<=n;i++)scanf("%d",&cost[i]);int x,y,z;for (int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);add(x,y,(ll)z);add(y,x,(ll)z);}if (!spfa(Inf)) return !printf("AFK");  //判断能否到达l=0;r=1000000000;while (l<=r)  //二分{mid=(l+r)/2;if (spfa(mid)) r=mid-1;else l=mid+1;}printf("%d\n",r+1);
}