通往奥格瑞玛的道路

题目背景

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

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

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

题目描述

在艾泽拉斯，有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：

说明

对于60%的数据，满足n≤200，m≤10000，b≤200

对于100%的数据，满足n≤10000，m≤50000，b≤1000000000

对于100%的数据，满足ci≤1000000000，fi≤1000000000，可能有两条边连接着相同的城市。

思路

二分+SPFA

两遍SPFA，一遍求可以到达那些城市，一遍求出ans.

代码实现

 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn=1e5+10;
 4 const int maxm=1e6+10;
 5 int n,m,hp;
 6 int a,b,c;
 7 int h[maxn],hs=1;
 8 int e_s[maxm],e_n[maxm],e_f[maxm];
 9 inline int max_(int x,int y){return x>y?x:y;}
10 int q[maxm],head,tail;
11 int hit[maxn];
12 bool v[maxn];
13 void SPFA1(int s){
14     memset(hit,0x7f,sizeof(hit));
15     hit[s]=0,q[head++]=s;
16     while(head>tail){
17         a=q[tail++];
18         for(int i=h[a];i;i=e_n[i])
19         if(0ll+hit[a]+e_f[i]<hit[e_s[i]]){
20             hit[e_s[i]]=hit[a]+e_f[i];
21             q[head++]=e_s[i];
22         }
23     }
24     for(int i=1;i<=n;i++) if(hit[i]<=hp) v[i]=1;
25 }
26 int f[maxn],fee[maxn];
27 void SPFA2(int s){
28     memset(fee,0x7f,sizeof(fee));
29     fee[s]=f[s];head=tail=0,q[head++]=s;
30     while(head>tail){
31         a=q[tail++];
32         for(int i=h[a];i;i=e_n[i])
33         if(max_(fee[a],f[e_s[i]])<fee[e_s[i]]){
34             fee[e_s[i]]=max_(fee[a],f[e_s[i]]);
35             q[head++]=e_s[i];
36         }
37     }
38 }
39 int main(){
40     scanf("%d%d%d",&n,&m,&hp);
41     for(int i=1;i<=n;i++) scanf("%d",&f[i]);
42     for(int i=1;i<=m;i++){
43         scanf("%d%d%d",&a,&b,&c);
44         ++hs,e_s[hs]=b,e_n[hs]=h[a],e_f[hs]=c,h[a]=hs;
45         ++hs,e_s[hs]=a,e_n[hs]=h[b],e_f[hs]=c,h[b]=hs;
46     }
47     SPFA1(1);
48     SPFA2(1);
49     if(v[n]) printf("%d
",fee[n]);
50     else puts("AFK");
51     return 0;
52 }