题解【洛谷P1948】[USACO08JAN]电话线Telephone Lines

题面

题解

很显然，答案满足单调性。

因此，可以使用二分答案求解。

考虑\(check\)的实现。

贪心地想，免费的\(k\)对电话线一定都要用上。

每次\(check\)时将小于\(mid\)的边权设为\(0\)，其它的设为\(1\)。

跑一边最短路判断\(\mathrm{dist[n]}\)是否\(\leq k\)即可。

代码

#include <bits/stdc++.h>
#define itn int
#define gI gi

using namespace std;

inline int gi()
{
    int f = 1, x = 0; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return f * x;
}

const int maxn = 10003;

int n, p, k, dist[maxn], vis[maxn];
vector <int> v[maxn], edge[maxn], f[maxn];

inline bool check(int x)
{
    for (int i = 1; i <= n; i+=1)
    {
        int len = f[i].size();
        for (int j = 0; j < len; j+=1)
        {
            if (f[i][j] <= x) edge[i][j] = 0;
            else edge[i][j] = 1;
        }
    }//重设边权
    queue <int> q;
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    vis[1] = 1;
    dist[1] = 0;
    q.push(1);
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        vis[u] = 0;
        int len = v[u].size();
        for (int i = 0; i < len; i+=1)
        {
            int vv = v[u][i], w = edge[u][i];
            if (dist[vv] > dist[u] + w)
            {
                dist[vv] = dist[u] + w;
                if (!vis[vv]) q.push(vv);
            }
        }
    }
    return dist[n] <= k;
}

int main()
{
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    n = gi(), p = gi(), k = gi();
    for (int i = 1; i <= p; i+=1)
    {
        int u = gi(), vv = gi(), w = gi();
        v[u].push_back(vv);
        v[vv].push_back(u);
        edge[u].push_back(w);
        edge[vv].push_back(w);//现边权
        f[u].push_back(w);
        f[vv].push_back(w);//原边权
    }
    int l = 0, r = 1000000000, ans = -1;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    printf("%d\n", ans);
    return 0;
}