```cpp
const int N = 1514, M = 11451;
int que[51459810], bg = 0, ed = 0;//[bg,ed)
int dis[N];
// bool vis[N];
void _01bfs(int mid) {
bg = 0, ed = 1, que[0] = 1;
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;
while(bg < ed) {
int &u = que[bg];
bg++;
for(int i = head[u], v = to[i]; i; i = ne[i], v = to[i])
if(w[i] <= mid && dis[v] > dis[u])
dis[v] = dis[u], que[--bg] = v;
else if(w[i] > mid && dis[v] > dis[u] + 1)
dis[v] = dis[u] + 1, que[ed++] = v;
}
}
bool major(int T = 1) {
int n = read(), m = read(), k = read();
while(m--) {
int u = read(), v = read(), w = read();
addd(u, v, w);
}
int l = -1, r = 1145810;
while(l + 1 < r) {
int mid = l + r >> 1;
_01bfs(mid);
if(dis[n] == 0x3f3f3f3f) return puts("-1");
if(dis[n] > k) l = mid;
else r = mid;
}
printf("%d\n", r);
return 0;
}
by y_kx_b @ 2023-01-30 11:49:53
发现手写双端队列根本不需要这么大,可改小后还是没O2就Wa#10/kk
by y_kx_b @ 2023-01-30 11:55:26
~~反正肯定有UB,再仔细看看?~~
by __My0217__ @ 2023-01-30 12:12:50
@[mouyumin110217](/user/784650) 我一直在找ub,就是找不到 qwq
~~而且不是厌氧才是ub吗~~
by y_kx_b @ 2023-01-30 12:37:09
死因:手写队列向前越界
队头指针不能太靠前,否则一堆 `push_front()` 操作直接把你越界。
调了两个小时,警钟撅烂。
by y_kx_b @ 2023-01-30 16:37:14