通信线路（解法二）

AcWing-340-通信线路

分析

见《进阶指南》第355页。

实现

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1010, M = 10010;
struct edge {
    int to, next, w;
};
edge e[2 * M];
int idx, head[N];
struct node {
    int u, v, w;
};
int n, m, k;
node rec[M];
int dis[N];
bool mark[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 ++;
}
int bfs_01 () {
    memset(mark, 0, sizeof(mark));
    memset(dis, 0x3f, sizeof(dis));
    
    deque<int> dq;
    dis[1] = 0;
    dq.push_back(1);
    while (!dq.empty()) {
        int cur = dq.front();
        dq.pop_front();
        if (mark[cur] == true) continue;
        mark[cur] = true;
        for (int i = head[cur]; i != -1; i = e[i].next) {
            int to = e[i].to, w = e[i].w;
            if (dis[cur] + w < dis[to]) {
                dis[to] = dis[cur] + w;
                if (w == 0) {
                    dq.push_front(to);
                } else {
                    dq.push_back(to);
                }
            }
        }
    }
    return dis[n];
}
bool check (int x) {
    idx = 0;
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= m; ++ i) {
        int u = rec[i].u, v = rec[i].v, w = rec[i].w;
        add_edge(u, v, w > x);
        add_edge(v, u, w > x);
    }
    return bfs_01() <= k;
}

int main () {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; ++ i)
        cin >> rec[i].u >> rec[i].v >> rec[i].w;
    
    int l = 0, r = 1000000 + 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid) == true)
            r = mid;
        else
            l = mid + 1;
    }
    cout << (l == 1000000 + 1 ? -1 : l) << endl;
    return 0;
}