在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士,他是部落的中坚力量
有一天他醒来后发现自己居然到了联盟的主城暴风城
在被众多联盟的士兵攻击后,他决定逃回自己的家乡奥格瑞玛
在艾泽拉斯,有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:
4 4 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3
输出样例#1:
10
对于60%的数据,满足n≤200,m≤10000,b≤200
对于100%的数据,满足n≤10000,m≤50000,b≤1000000000
对于100%的数据,满足ci≤1000000000,fi≤1000000000,可能有两条边连接着相同的城市。
二分答案+SPFA
注意要开long long 啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #define lli long long int
7 using namespace std;
8 void read(lli & n)
9 {
10 char c='+';lli x=0;
11 while(c<'0'||c>'9')
12 c=getchar();
13 while(c>='0'&&c<='9')
14 {
15 x=x*10+(c-48);
16 c=getchar();
17 }
18 n=x;
19 }
20 const lli MAXN=100001;
21 const lli maxn=0x7fffffff;
22 struct node
23 {
24 lli u,v,w,nxt;
25 }edge[MAXN];
26 lli head[MAXN];
27 lli num=1;
28 lli dis[MAXN];
29 lli vis[MAXN];
30 lli n,m,maxnblood;
31 lli spend[MAXN];
32 lli l=0x7fffffff,r=-1;
33 void add_edge(lli x,lli y,lli z)
34 {
35 edge[num].u=x;
36 edge[num].v=y;
37 edge[num].w=z;
38 edge[num].nxt=head[x];
39 head[x]=num++;
40 }
41 lli SPFA(lli r)
42 {
43 if(r<spend[1])
44 {return 0;}
45 for(lli i=1;i<=n+1;i++)
46 dis[i]=maxn,vis[i]=0;
47 queue<int>q;
48 q.push(1);
49 vis[1]=1;
50 dis[1]=0;
51 while(q.size()!=0)
52 {
53 lli p=q.front();
54 q.pop();
55 vis[p]=0;
56 for(lli i=head[p];i!=-1;i=edge[i].nxt)
57 {
58 lli will=edge[i].v;
59 if((dis[will]>dis[p]+edge[i].w)&&spend[will]<=r)
60 {
61 dis[will]=dis[p]+edge[i].w;
62 if(vis[will]==0)
63 {
64 vis[will]=1;
65 q.push(will);
66 }
67 }
68 }
69 }
70 if(dis[n]<=maxnblood)
71 return 1;
72 else
73 return 0;
74 }
75 int main()
76 {
77 read(n);read(m);read(maxnblood);
78 for(lli i=1;i<=n;i++)
79 head[i]=-1;
80 for(lli i=1;i<=n;i++)
81 {
82 read(spend[i]);
83 l=min(spend[i],l);
84 r=max(spend[i],r);
85 }
86 for(lli i=1;i<=m;i++)
87 {
88 lli x,y,z;
89 read(x);read(y);read(z);
90 add_edge(x,y,z);
91 add_edge(y,x,z);
92 }
93 lli ans=0;
94 while(l<=r)
95 {
96 lli mid=(l+r)/2;
97 if(SPFA(mid))
98 {
99 ans=mid;
100 r=mid-1;
101 }
102 else l=mid+1;
103 }
104 //printf("%d",r);
105 if(ans&&SPFA(ans))
106 printf("%d",ans);
107 else
108 printf("AFK");
109 return 0;
110 }