忘れ潮 @ 2021-09-09 22:28:40
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, z, blood, cnt, head[100005], cost[10005], f[10005], vis[10005];
struct node{
int to, next, dis;
}e[100005];
struct point{
int blod, maxn, p;
point(int i, int j, int k){
blod = i, maxn = j, p = k;
}
};
queue <point> q;
void add(int u, int v, int d){
e[++cnt].dis = d;
e[cnt].next = head[u];
e[cnt].to = v;
head[u] = cnt;
}
int main(){
memset(f, 0x3f, sizeof(f));
scanf("%d%d%d", &n, &m, &blood);
for(int i = 1; i <= n; i++)
scanf("%d", &cost[i]);
for(int i = 1; i <= m; i++){
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
add(y, x, z);
}
vis[1] = 1;
f[1] = cost[1];
q.push(point(blood, cost[1], 1));
while(!q.empty()){
int u = q.front().p, b = q.front().blod, temp = q.front().maxn;
q.pop();
vis[u] = 0;
for(int i = head[u]; i; i = e[i].next){
int v = e[i].to, w = e[i].dis;
if(b < w) continue;
if(f[v] > max(cost[v], temp)){
f[v] = max(cost[v], temp);
if(!vis[v]) vis[v] = 1, q.push(point(b - w, max(cost[v], temp), v));
}
}
}
if(f[n] != 1061109567) printf("%d", f[n]);
else printf("AFK");
return 0;
}