题目背景
在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量
有一天他醒来后发现自己居然到了联盟的主城暴风城
在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛
题目描述
在艾泽拉斯，有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。
6月离开机房准备期末考试的最后一道题。
一个月之后才来写题解QAQ。
题目设问为：最多的一次收取的费用的最小值是多少。那么就基本可以确定是二分。
二分？题目设问求费用，那我们二分费用好了。
左边界为l==1，右边界就是全部的点权之和。【这里注意开long long 】! 否则会wa3个点。
void binary() { ll l=1,r=sum; while(l<r) { ll mid=(l+r)>>1; if(spfa_check(mid)) r=mid; else l=mid+1; } ans=l; }
最短路？我们求最短路的目的是看血量是否满足要求。在这里起点和终点都是确定的。
在基本的最短路（这里用的是spfa）上加一个条件：走到的这个点的点权是否满足小于我们二分出的花费。
跑完一遍，如果dis[n]小于血量，则可行，可继续二分。
for(int i=head[x];i;i=edge[i].next) { int y=edge[i].to; if(dis[y]>dis[x]+edge[i].val&&f[y]<=cnt) { dis[y]=dis[x]+edge[i].val; if(visit[y]==0) { visit[y]=1; q.push(y); } } }
跑最短路的时候记得每次都要初始化一下。
无解判定？我们可以在最开始让花的费用等于inf，进行一遍spfacheck，在如此宽松的条件下都不可行，那必是无解了！输出AFK。
code
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int inf=0x3f3f3f3f; 5 int n,m,b,tot,f[20000],u[20000],head[20000],dis[20000]; 6 bool visit[20000]; 7 ll ans,sum; 8 struct node{ 9 int to,next,val; 10 }edge[110000]; 11 void add(int x,int y,int z) 12 { 13 edge[++tot].to=y; 14 edge[tot].val=z; 15 edge[tot].next=head[x]; 16 head[x]=tot; 17 } 18 bool spfa_check(ll cnt) 19 { 20 memset(visit,0,sizeof(visit)); 21 queue<int>q; 22 for(int i=1;i<=n;i++) dis[i]=inf; 23 dis[1]=0; 24 visit[1]=1; 25 q.push(1); 26 while(!q.empty()) 27 { 28 int x=q.front(); 29 q.pop();visit[x]=0; 30 for(int i=head[x];i;i=edge[i].next) 31 { 32 int y=edge[i].to; 33 if(dis[y]>dis[x]+edge[i].val&&f[y]<=cnt) 34 { 35 dis[y]=dis[x]+edge[i].val; 36 if(visit[y]==0) 37 { 38 visit[y]=1; 39 q.push(y); 40 } 41 } 42 } 43 } 44 if(dis[n]<b) return true; 45 else return false; 46 } 47 void binary() 48 { 49 ll l=1,r=sum; 50 while(l<r) 51 { 52 ll mid=(l+r)>>1; 53 if(spfa_check(mid)) r=mid; 54 else l=mid+1; 55 } 56 ans=l; 57 } 58 int main() 59 { 60 scanf("%d%d%d",&n,&m,&b); 61 for(int i=1;i<=n;i++) 62 scanf("%d",&f[i]),sum+=f[i]; 63 for(int i=1;i<=m;i++) 64 { 65 int x=0,y=0,z=0; 66 scanf("%d%d%d",&x,&y,&z); 67 if(x==y) continue; 68 add(x,y,z); 69 add(y,x,z); 70 } 71 if(!spfa_check(inf)) 72 { 73 printf("AFK "); 74 return 0; 75 } 76 binary(); 77 printf("%lld",ans); 78 return 0; 79 }