通信线路（解法一）

AcWing-340-通信线路

分析

见《进阶指南》第355页。

实现

#include <iostream>
#include <cstring>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 1010, M = 20010;
struct edge {
    int to, next, w;
};
edge e[M];
int idx, head[N];
struct node {
    int idx, layer, dis;
    bool operator < (const node& o) const {
        return dis > o.dis;
    }
};
int n, m, k;
int dis[N][N];
bool mark[N][N];

void add_edge (int u, int v, int w) {
    e[idx].w = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
void dijkstra () {
    memset(dis, 0x3f, sizeof(dis));
    
    priority_queue<node> pq;
    dis[1][0] = 0;
    pq.push({ 1, 0, dis[1][0] });
    while (!pq.empty()) {
        int cur = pq.top().idx, layer = pq.top().layer;
        pq.pop();
        if (mark[cur][layer] == true) continue;
        mark[cur][layer] = true;
        for (int i = head[cur]; i != -1; i = e[i].next) {
            int to = e[i].to, w = e[i].w;
            if (max(dis[cur][layer], w) < dis[to][layer]) {
                dis[to][layer] = max(dis[cur][layer], w);
                pq.push({ to, layer, dis[to][layer] });
            }
            if (layer < k && dis[cur][layer] < dis[to][layer + 1]) {
                dis[to][layer + 1] = dis[cur][layer];
                pq.push({ to, layer + 1, dis[to][layer + 1] });
            }
        }
    }
}

int main () {
    memset(head, -1, sizeof(head));
    cin >> n >> m >> k;
    for (int i = 1, u, v, w; i <= m; ++ i) {
        cin >> u >> v >> w;
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    dijkstra();
    int res = inf;
    for (int i = 0; i <= k; ++ i)
        res = min(res, dis[n][i]);
    cout << (res == inf ? -1 : res) << endl;
    return 0;
}