堆优化dijkstra作check函数 133ms
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1e3 + 10, P = 1e4 + 10;
int n, p, k;
int h[N], e[P << 1], w[P << 1], ne[P << 1], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool check(int bound) {
memset(dist, 0x3f, sizeof(dist));
memset(st, 0, sizeof(st));
priority_queue<PII, vector<PII>, greater<PII>> heap;
dist[1] = 0;
heap.push({dist[1], 1});
while (!heap.empty()) {
PII cur = heap.top(); heap.pop();
int t = cur.y;
if (st[t]) continue;
st[t] = true;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i], val = w[i] > bound;
if (dist[j] > dist[t] + val) {
dist[j] = dist[t] + val;
heap.push({dist[j], j});
}
}
}
return dist[n] <= k;
}
int main() {
memset(h, -1, sizeof(h));
scanf("%d%d%d", &n, &p, &k);
int a, b, c;
while (p--) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
int l = 0, r = 1000001;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
if (l == 1000001) l = -1;
printf("%d", l);
return 0;
}
双端队列作check函数 54ms
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, P = 1e4 + 10;
int n, p, k;
int h[N], e[P << 1], w[P << 1], ne[P << 1], idx;
int dist[N];
bool st[N];
deque<int> dq;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool check(int bound) {
memset(dist, 0x3f, sizeof(dist));
memset(st, 0, sizeof(st));
dist[1] = 0;
dq.push_back(1);
while (!dq.empty()) {
int t = dq.front(); dq.pop_front();
if (st[t]) continue;
st[t] = true;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i], val = w[i] > bound;
if (dist[j] > dist[t] + val) {
dist[j] = dist[t] + val;
if (!val) dq.push_front(j);
else dq.push_back(j);
}
}
}
return dist[n] <= k;
}
int main() {
memset(h, -1, sizeof(h));
scanf("%d%d%d", &n, &p, &k);
int a, b, c;
while (p--) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
int l = 0, r = 1000001;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
if (l == 1000001) l = -1;
printf("%d", l);
return 0;
}