luogu P1462 通往奥格瑞玛的道路

分析

以前做过这类题，就是二分歪嘴哦所能接受的费用最大值，然后以此为上限，跑spfa，看是否能够到达终点，如果能，调小上界，不能，调大下界，然后就不断对res（答案变量）取min，最后的res就是答案

code

#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(int i=start;i<=end;++i)//能卡点常就卡点呗
#define clean(arry,num); memset(arry,num,sizeof(arry));
#define min(a,b) ((a>b)?b:a)
#define ll long long
int n,m,b,cnt=0;
const int maxn=10000+10;
const int maxm=50000+10;
int f[maxn];
struct node{int e;int blood;int nxt;}edge[maxm<<1];
int head[maxn];
ll dis[maxn];//注意开long long,不然爆精度
inline int read()
{
	int ans=0;bool neg=false;char r=getchar();
	while(r>'9'||r<'0'){if(r=='-')neg=true;r=getchar();}
	while(r>='0'&&r<='9'){ans=ans*10+r-'0';r=getchar();}
	return (neg)?-ans:ans;
}
//helps are always given in Hogwarts
inline void addl(int u,int v,int bl)
{
	edge[cnt].blood=bl;
	edge[cnt].e=v;
	edge[cnt].nxt=head[u];
	head[u]=cnt++;
}
void spfa(int maxfee)
{
	clean(dis,0x7f);
	dis[1]=0;
	deque<int>q;
	q.push_back(1);
	while(!q.empty())
	{
		int u=q.front();q.pop_front();
		for(int i=head[u];i!=-1;i=edge[i].nxt)
		{
			int v=edge[i].e;int cost=edge[i].blood;
			if(f[v]<=maxfee&&dis[v]>dis[u]+cost)//如果满足三角形不等式且新节点的花费在max之下就松弛
			{
				dis[v]=dis[u]+cost;
				if(!q.empty()&&dis[v]<dis[q.front()])q.push_front(v);
				else q.push_back(v);//slf优化
			}
		}
	}
}
inline void bin()//二分模块
{
	
	int maxfee=1000000000,minfee=0;
	int res=INT_MAX;
	while(maxfee>=minfee)
	{
		int mid=minfee+((maxfee-minfee)>>1);//mid=l+(r-l)/2,这样不会爆int
		spfa(mid);
		if(dis[n]<=b)
		{
			res=min(res,mid);
			maxfee=mid-1;
		}
		else minfee=mid+1;	
	}
	if(res==INT_MAX)printf("AFK");
	else printf("%d",res);
}
int main()
{
	#ifndef ONLINE_JUDGE
    freopen("datain2.txt","r",stdin);
    #endif
    n=read(),m=read(),b=read();
    clean(head,-1);
    loop(i,1,n)f[i]=read();
    loop(i,1,m)
    {
    	int ai,bi,ci;
    	ai=read(),bi=read(),ci=read();
    	addl(ai,bi,ci);
    	addl(bi,ai,ci);
	}
	bin();
	return 0;
}