P1462 通往奥格瑞玛的道路

P1462 通往奥格瑞玛的道路

题目背景

在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量

有一天他醒来后发现自己居然到了联盟的主城暴风城

在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛

题目描述

在艾泽拉斯，有n个城市。编号为1,2,3,...,n。

城市之间有m条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。

每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。

假设1为暴风城，n为奥格瑞玛，而他的血量最多为b，出发时他的血量是满的。

歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。

#include<bits/stdc++.h>
using namespace std;
#define maxn 10010
#define maxm 50010
#define maxb 1000000000
#define maxc 1000000000
#define maxf 1000000000

struct Edge{
	int next;
	int to;
	int w;
}edge[2*maxm];
int head[maxn];
int t=0;
void addEdge(int u,int v,int c){
	t++;
	edge[t].to=v;
	edge[t].w=c;
	edge[t].next=head[u];
	head[u]=t;
}

int n,m,b,f[maxn];
int vis[maxn]={0};
int d[maxn];

priority_queue< pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> >  > q;//定义小根堆。 

int Dijkstra(int x){
	if(x<f[1]||x<f[n]) return 0;//1、n 花费大于总花费，则不可能 
	for(int i=1;i<=n;i++) { d[i]=maxc;}
	memset(vis,0,sizeof(vis));
	d[1]=0;
	q.push( make_pair(0,1) );
	
	while(!q.empty()){
		int p=q.top().second;
		q.pop();
		if(vis[p]) continue;
		vis[p]=1;
		int s=head[p];
		while(s){
			if(f[edge[s].to]<=x&&vis[edge[s].to]==0&&d[edge[s].to]>d[p]+edge[s].w){
				d[edge[s].to]=d[p]+edge[s].w;
				q.push( make_pair(d[edge[s].to],edge[s].to) );
			}
			s=edge[s].next;
		}
	}
	if(d[n]<b) return 1;
	return 0;
}
int main(){
	std::ios::sync_with_stdio(false);
	
	cin>>n>>m>>b;
	for(int i=1;i<=n;i++){ cin>>f[i]; }
	int u,v,c;
	for(int i=0;i<m;i++){ 
	    cin>>u>>v>>c;
	    addEdge(u,v,c);
	    addEdge(v,u,c);
	}
	
	if(Dijkstra(maxf)==0){//最大花费过不了 
        cout<<"AFK"<<endl;
        return 0;
    } 
    
	int l=1,r=maxf;
	while(l<=r){//二分查找最小花费
		mid=(l+r)>>1;
		if(Dijkstra(mid)) r=mid-1;
		else  l=mid+1;
	}
	cout<<l<<endl;
	return 0;
}