题目链接

Telephone Lines POJ - 3662

思路

$$ 假设可行解为X，长度小于等于X的边值为0,大于X的边为1,跑一下最短路验证一下，如果最短路长度大于K，则不满足条件。 $$

时间复杂度

$$ O(log(max(L_i))Mlog(N)) $$

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

const long long INF = 1e18;

class Dij {
public:

    typedef long long T;

    // .first = v
    // .second.first = w;
    // .second.second = next;
    vector<int> head;
    typedef pair<int, pair<T, int> > P;
    vector<P> e;
    int tot;
    vector<T> dist;


    inline void init(int cnt_n, int cnt_m) {
        head.resize(cnt_n + 5);
        dist.resize(cnt_n + 5);
        fill(head.begin(), head.end(), -1);
        e.resize(cnt_m * 2 + 10);
        tot = 0;
    }

    inline void add_edge(int u, int v, T w) {
        e[tot] = make_pair(v, make_pair(w, head[u]));
        head[u] = tot++;
    }

    inline void add_edges(int u, int v, T w) {
        add_edge(u, v, w);
        add_edge(v, u, w);
    }


    void gao(int s) {
        priority_queue<pair<T, int>
                 , vector<pair<T, int> >
                 , greater<pair<T, int> > > sm;
        fill(dist.begin(), dist.end(), INF);
        dist[s] = 0;
        sm.push(make_pair(0, s));

        while (!sm.empty()) {
            pair<T, int> p = sm.top();
            sm.pop();
            int u = p.second;
            if (dist[u] < p.first) {
                continue;
            }
            for (int i = head[u]; ~i; i = e[i].second.second) {
                int v = e[i].first;
                T w = e[i].second.first;
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    sm.push(make_pair(dist[v], v));
                }
            }
        }
    }
} dij;

const int MAXN = 1e4 + 10;
int n, m, k;
int a[MAXN], b[MAXN], c[MAXN];

bool check(int mid) {
    dij.init(n, m);
    for (int i = 1; i <= m; i++) {
        if (c[i] <= mid) {
            dij.add_edges(a[i], b[i], 0);
        } else {
            dij.add_edges(a[i], b[i], 1);
        }
    }
    dij.gao(1);
    if (dij.dist[n] <= k) {
        return true;
    } else {
        return false;
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &k);// don't forget &
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &a[i], &b[i], &c[i]);// don't forget &
    }
    int l = 0, r = 1e6, ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    printf("%d", ans);
    return 0;
}