https://www.luogu.com.cn/problem/P1462

题目背景

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

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

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

题目描述

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

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

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

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

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

输入格式

第一行3个正整数，n，m，b。分别表示有n个城市，m条公路，歪嘴哦的血量为b。

接下来有n行，每行1个正整数，fi。表示经过城市i，需要交费fi元。

再接下来有m行，每行3个正整数，ai，bi，ci(1<=ai，bi<=n)。表示城市ai和城市bi之间有一条公路，如果从城市ai到城市bi，或者从城市bi到城市ai，会损失ci的血量。

输出格式

仅一个整数，表示歪嘴哦交费最多的一次的最小值。

如果他无法到达奥格瑞玛，输出AFK。

输入输出样例

输入 #1

1
2
3
4
5
6
7
8
9
4 4 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3

输出 #1

1
10

对所有的缴费排序，二分判断每个最大缴费是否可行。

开始 优先队列 一直压点…蠢哭…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
const ll INF=0x3f3f3f3f3f3f3f3f;
const int MAX=10000+10;
int n,m,b,vis[MAX],fi[MAX],d[MAX],ai,bi,ci,ans=0;
ll low[MAX];
struct Edge{
	int to,next,c;
}edge[10*MAX];
int head[MAX],tot;
void init(){
	tot=0;
	memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int c){
	edge[tot].to=v;
	edge[tot].c=c;
	edge[tot].next=head[u];
	head[u]=tot++;
}
struct node{
	int i;
	ll c;
	bool operator<(const node &x)const{
        return c>x.c;
    }
    node(int _i,ll _c){
    	i=_i;
    	c=_c;
    }
};
void dij(int s,int high){
	priority_queue<node> q;
	fi(i,1,n+1){
		vis[i]=false;
		low[i]=INF;
	}
	if(d[s] > high) return;//第一个点就不符合 
	low[s]=0;
	q.push(node(s,0));
	while(!q.empty()){
		node cur=q.top();
		q.pop();
		int v=cur.i;
		ll lowv=cur.c;
		if(vis[v]) continue;
		vis[v]=1;
		for(int i=head[v];i!=-1;i=edge[i].next){
			int t=edge[i].to;
			int c=edge[i].c;
			if(fi[t] <= high && lowv + c < low[t]){
				low[t] = lowv + c;
				q.push(node(t,low[t]));
			}
		}
	}
}
int main(){
	freopen("in","r",stdin);
	sf(n);sf(m);sf(b);
	fi(i,1,n+1){
		sf(fi[i]);
		d[i]=fi[i];
	}
	sort(d+1,d+1+n);
	init();
	fi(i,1,m+1){
		sf(ai);sf(bi);sf(ci);
		addedge(ai,bi,ci);
		addedge(bi,ai,ci);
	}
	int l=1,r=n;
	while(l<=r){
		int m=(l+r)/2;
		dij(1,d[m]);
		if(low[n]>b){ 
			l=m+1;
		}else{
			ans=d[m];
			r=m-1;
		} ;
	}
	if(ans) pf(ans);
	else pfc("AFK");
	return 0;
}