POJ3662或洛谷1948 Telephone Lines

二分答案+单源最短路

POJ原题链接

洛谷原题链接

显然可以二分答案，检验\(mid\)可以使用最短路来解决。
将大于\(mid\)的边看成长度为\(1\)的边，说明要使用免费升级服务，否则长度为\(0\)边，即不需要占免费的资格。
然后就可以在上面跑最短路，如果\(dis[n]>k\)说明该答案不可行，将答案改大，否则说明可行，往小的去尝试。
而针对长度只有\(0,1\)的图可以使用双端队列的\(BFS\)来解决，不过我这种懒人就直接跑\(SPFA\)了。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
const int M = 1e4 + 10;
int fi[N], ne[M << 1], di[M << 1], da[M << 1], dis[N], a[M], q[M << 1], l, k, n;
bool v[N];
int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c<'0' || c>'9'; c = getchar())
        p = (c == '-' || p) ? 1 : 0;
    for (; c >= '0'&&c <= '9'; c = getchar())
        x = x * 10 + (c - '0');
    return p ? -x : x;
}
inline void add(int x, int y, int z)
{
    di[++l] = y;
    da[l] = z;
    ne[l] = fi[x];
    fi[x] = l;
}
bool judge(int o)
{
    memset(dis, 60, sizeof(dis));
    memset(v, 0, sizeof(v));
    int i, x, y, z, head = 0, tail = 1;
    dis[1] = 0;
    q[1] = 1;
    while (head != tail)
    {
        x = q[++head];
        v[x] = 0;
        for (i = fi[x]; i; i = ne[i])
        {
            y = di[i];
            z = da[i] > o ? 1 : 0;
            if (dis[y] > dis[x] + z)
            {
                dis[y] = dis[x] + z;
                if (!v[y])
                {
                    q[++tail] = y;
                    v[y] = 1;
                }
            }
        }
    }
    if (dis[n] > k)
        return false;
    return true;
}
int main()
{
    int i, m, x, y, ll, r, mid, an = -1;
    n = re();
    m = re();
    k = re();
    for (i = 1; i <= m; i++)
    {
        x = re();
        y = re();
        a[i] = re();
        add(x, y, a[i]);
        add(y, x, a[i]);
    }
    sort(a + 1, a + m + 1);
    ll = 0;
    r = m;
    while (ll <= r)
    {
        mid = (ll + r) >> 1;
        if (judge(a[mid]))
        {
            r = mid - 1;
            an = a[mid];
        }
        else
            ll = mid + 1;
    }
    printf("%d", an);
    return 0;
}

ps：因为我用的是\(VS\)，所以代码会自动补空格，而我本来的风格是没有空格的。

POJ3662或洛谷1948 Telephone Lines

原文：https://www.cnblogs.com/Iowa-Battleship/p/9535184.html