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
85
86
87
88
89
90
91
92
93
94
95
96
|
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
const int maxn = 100005;
#define INF 0x3f3f3f3f
long long cost[maxn];
int n, m, head[maxn], dis[maxn];
#define pp pair<int,int>
#define mp make_pair
long long b,cnt;
bool vis[maxn];
struct
{
int nex, v, val;
}edge[maxn];
void add(int u,int v,int val)
{
edge[++cnt].val = val;
edge[cnt].v = v;
edge[cnt].nex = head[u];
head[u] = cnt;
}
priority_queue<pp, vector<pp>, greater<pp> > q;
bool dij(long long x)
{
while(!q.empty()) q.pop();
if(cost[1]>x)
return 0;
memset(dis, INF, sizeof dis);
memset(vis, 0, sizeof vis);
q.push(mp(0, 1));
dis[1] = 0;
while(!q.empty())
{
int u = q.top().second;
q.pop();
if(vis[u])
continue;
vis[u] = 1;
for (int i = head[u]; i;i=edge[i].nex)
{
int val = edge[i].val;
int v = edge[i].v;
if(cost[v]>x)
continue;
if(dis[v]>dis[u]+val)
{
dis[v] = dis[u] + val;
q.push(mp(dis[v], v));
}
if(v==n)
{
if(dis[n]>=b)
return 0;
else
return 1;
}
}
}
return 0;
}
int main()
{
cin >> n >> m >> b;
long long Max = 0;
for (int i = 1; i <= n;i++)
{
cin >> cost[i];
Max = max(Max, cost[i]);
}
for (int i = 1; i <= m;i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
long long l = 1, r = Max, ans = -1;
while(l<=r)
{
long long mid = l + r >> 1;
if(dij(mid)){
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
if(ans!=-1)
cout<<ans<<endl;
else
cout<<"AFK"<<endl;
}
|
近期评论