分层图

#include <bits/stdc++.h>
using namespace std;

const int N = 1005, M = 10005 * 2;

int head[N], nxt[M], edge[M], ver[M], tot;
int n, m, k;
int dist[N][N];
bool v[N][N];
struct node {
    int x, dist, state;
    bool operator< (const node &w)const {
        return dist < w.dist;
    }
};

void add(int x, int y, int z) {
    ver[++ tot] = y, nxt[tot] = head[x], edge[tot] = z, head[x] = tot;
}

void dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1][0] = 0;
    priority_queue<node> q;
    q.push({1, 0, 0});
    while(q.size()) {
        int x = q.top().x, state = q.top().state; q.pop();
        if(v[x][state]) continue;
        v[x][state] = true;
        for(int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if(dist[y][state] > max(dist[x][state], edge[i])) {
                dist[y][state] = max(dist[x][state], edge[i]);
                q.push({y, -dist[y][state], state});
            }
            if(state < k && dist[y][state + 1] > dist[x][state]) {
                dist[y][state + 1] = dist[x][state];
                q.push({y, -dist[y][state + 1], state + 1});
            }
        }
    }
}

int main() {
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i ++ ) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z), add(y, x, z);
    }
    dijkstra();
    int ans = 1 << 30;
    for(int i = 0; i <= k; i ++ ) ans = min(ans, dist[n][i]);
    cout << (ans == 0x3f3f3f3f ? -1 : ans) << endl;
    return 0;
}

二分答案

#include <bits/stdc++.h>
using namespace std;

const int N = 1005, M = 10005 * 2;

int head[N], nxt[M], ver[M], edge[M], tot;
int n, m, k;
int dist[N];
bool v[N];

void add(int x, int y, int z) {
    ver[++ tot] = y, nxt[tot] = head[x], edge[tot] = z, head[x] = tot;
}

bool check(int mid) {
    deque<int> q;
    memset(dist, 0x3f, sizeof dist);
    memset(v, 0, sizeof v);
    q.push_front(1);
    dist[1] = 0;
    while(q.size()) {
        int x = q.front(); q.pop_front();
        if(v[x]) continue;
        v[x] = true;
        for(int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if(dist[y] > dist[x] + (edge[i] > mid)) {
                dist[y] = dist[x] + (edge[i] > mid);
                if(edge[i] > mid) q.push_back(y);
                else q.push_front(y);
            }
        }
    }
    return dist[n] <= k;
}

int main() {
    cin >> n >> m >> k;
    for(int i = 0; i < m; i ++ ) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z), add(y, x, z);
    }
    int l = 0, r = 1000001;
    while(l < r) {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << (l == 1000001 ? -1 : l) << endl;
    return 0;
}