洛谷 P1948 [USACO08JAN] Telephone Lines S（二分+01BFS）

题目链接

https://www.luogu.com.cn/problem/P1948

思路

这是一道非常经典的题。

我们考虑二分最大的花费$x$，然后将边权大于$x$的边权看作$1$，小于等于$x$的边权看作$0$。

用01BFS求$1$号节点到$n$号节点的最短路径，如果$dist[n]\le k$，则表示当前的$x$为可行解。

代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

typedef long long i64;
typedef unsigned long long u64;
typedef pair<int, int> pii;

const int N = 1e3 + 5, M = 1e4 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;

int n, p, k;
int dist[N];
bool st[N];
int a[M], b[M], l[M];
vector<pii>mp[N];
bool bfs(int x)
{
    fill(dist + 1, dist + 1 + n, inf);
    fill(st + 1, st + 1 + n, false);
    deque<int>q;
    dist[1] = 0;
    q.push_back(1);
    while (q.size())
    {
        int u = q.front();
        q.pop_front();
        if (st[u]) continue;
        st[u] = true;
        for (auto [v, w] : mp[u])
        {
            int d = w > x;
            if (dist[v] > dist[u] + d)
            {
                dist[v] = dist[u] + d;
                if (d)
                {
                    q.push_back(v);
                }
                else q.push_front(v);
            }
        }
    }
    return dist[n] <= k;
}
void solve(int test_case)
{
    cin >> n >> p >> k;
    for (int i = 1; i <= p; i++)
    {
        cin >> a[i] >> b[i] >> l[i];
        mp[a[i]].push_back({b[i], l[i]});
        mp[b[i]].push_back({a[i], l[i]});
    }
    int maxx = *max_element(l + 1, l + 1 + p);
    int low = 0, high = maxx + 1;
    while (low < high)
    {
        int mid = low + high >> 1;
        if (bfs(mid))
        {
            high = mid;
        }
        else low = mid + 1;
    }
    if (high == maxx + 1) high = -1;
    cout << high << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; i++)
    {
        solve(i);
    }
    return 0;
}

原文地址：https://blog.csdn.net/weixin_74754298/article/details/143751077

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！