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

· · 题解

比较套路的一道题。

首先可以想到是要二分这个费用，然后我们思考如何check他合不合法。

一个比较妙的思路就是，我们把整个图上所有大于mid的边赋为0，所有小于等于mid的边赋值为1，这样的话只需要跑一边bfs，然后看到终点的距离是否小于等于k即可.

时间复杂度O(NlogN)

Code: 
#include <bits/stdc++.h>

using namespace std;

int n , p , k, ans=-1;
int l = 1, r;

const int N = 1e4 + 10;

struct Edge {
    int to , nxt , w;
}e[N << 1];

int head[N] , cnt;
void add(int u , int v  ,int w) {
    e[++ cnt].to = v;
    e[cnt].w = w;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}

bool inq[N];
int dis[N];
bool check(int x) {
    queue <int> q;
    q.push(1);
    for(int i = 2 ; i <= n ; ++ i) dis[i] = 0x3f3f3f3f;
    inq[1] = 1; dis[1] = 0;
    while(!q.empty()) {
        int now = q.front(); q.pop();
        inq[now] = 0;
        for(int i = head[now] ; i ; i = e[i].nxt) {
            int v = e[i].to , w = e[i].w;
            if(w <= x) w = 0; 
            else w = 1;
            if(dis[v] > dis[now] + w) {
                dis[v] = dis[now] + w;
                if(!inq[v]) inq[v] = 1 , q.push(v); 
            }
        }
    }
    return dis[n] <= k;
} 

int main () {
    scanf("%d %d %d" , &n , &p , &k);
    for(int i = 1 ;  i <= p ; ++ i) {
        int u , v , w;
        scanf("%d %d %d" , &u , &v, &w);
        add(u , v , w); add(v  , u , w); 
        r += w;
    }
    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;
}