Sora1336 @ 2022-09-06 20:54:30
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1e4 + 5;
const int maxm = 5e4 + 5;
const int inf = 0x3f3f3f3f;
struct E {
int nxt, to, val;
} e[maxn << 1];
int n, m, k, head[maxn], cnt, dis[maxn], a[maxn];
bool vis[maxn];
void add(int x, int y, int z) {
e[++ cnt].to = y;
e[cnt].val = z;
e[cnt].nxt = head[x];
head[x] = cnt;
}
struct node {
int pos, w;
friend bool operator < (node a, node b) {
return a.w > b.w;
}
} tmp;
priority_queue<node> q;
bool judge(int qwe) {
for(int i = 1; i <= n; i ++)
dis[i] = -1;
memset(vis, 0, sizeof(vis));
dis[1] = k;
tmp.pos = 1, tmp.w = k;
q.push(tmp);
while(!q.empty()) {
int u = q.top().pos;
int d = q.top().w;
q.pop();
if(dis[u]!=d) continue;
if(vis[u]) continue;
else vis[u] = 1;
for(int i = head[u]; i; i = e[i].nxt) {
if(a[e[i].to] > qwe) continue;
if(dis[e[i].to] < dis[u] - e[i].val && dis[u] - e[i].val >= 0) {
dis[e[i].to] = dis[u] - e[i].val;
tmp.pos = e[i].to, tmp.w = dis[e[i].to];
q.push(tmp);
}
}
}
return (dis[n] != -1);
}
int main() {
scanf("%d%d%d", &n, &m, &k);
int l = inf, r = 0;
for(int i = 1; i <= n; i ++) {
scanf("%d",a + i);
l = min(l, a[i]);
r = max(r, a[i]);
}
int flg = r;
for(int i = 1, a, b, c; i <= m; i ++) {
scanf("%d%d%d",&a,&b,&c);
add(a, b, c);
add(b, a, c);
}
while(l - 1 < r) {
int mid = l + r >> 1;
if(judge(mid)) r = mid - 1;
else l = mid + 1;
}
if(l == flg + 1) cout << "AFK" << endl;
else cout << l << endl;
}
by Haber @ 2022-09-06 21:10:26
可以尝试使用 l=0,r=0x3f3f3f3f
试一下?
by Sora1336 @ 2022-09-06 21:14:56
@Habers 没用/kk
by Haber @ 2022-09-06 21:24:52
@Sora1336 您为啥 dis
赋成 -1
?
by Haber @ 2022-09-06 21:25:37
阿西,这波 Dij 完全没看懂hh。