POJ 3662 Telephone Lines

3662 -- Telephone Lines
　K + 1番目に長い辺の長さkLの値を二分探索する。
　二分探索の中ではmaxkLより長い辺のコストを1，短い辺のコストを0とし、合計コストK以内で着けるかどうかを見る。
　これは0-1BFS(http://hos.ac/slides/20110504_graph.pdfを参照)でできる。

#include <vector>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)

const int INF = 1e9;
typedef priority_queue<int, vector<int>, greater<int> > pque;

int N, P, K;
vector<pair<int, int> > adj[1000];
int cost[1000];
bool ok(int maxL) {
    fill_n(cost, 1000, INF);
    deque<int> deq;
    deq.push_front(0); cost[0] = 0;
    while(!deq.empty()) {
        int cur_v = deq.front(); deq.pop_front();
        if(cost[cur_v] > K) return false;
        if(cur_v == N - 1) return true;
        rep(i, adj[cur_v].size()) {
            int nxt_v = adj[cur_v][i].first, nL = adj[cur_v][i].second;
            int ncos = nL > maxL ? 1 : 0;
            if(cost[nxt_v] > cost[cur_v] + ncos) {
                cost[nxt_v] = cost[cur_v] + ncos;
                if(ncos == 0)
                  deq.push_front(nxt_v);
                else
                  deq.push_back(nxt_v);
            }
        }
    }
    return false;
}
int main() {
    scanf("%d%d%d", &N, &P, &K);
    rep(i, P) {
        int a, b, l;
        scanf("%d%d%d", &a, &b, &l);
        --a; --b;
        adj[a].push_back(make_pair(b, l));
        adj[b].push_back(make_pair(a, l));
    }
    
    int lb = -1, ub = 1000010;
    if(ok(ub) == false) {
        puts("-1");
        return 0;
    }
    while(ub - lb > 1) {
        int mid = (ub + lb) / 2;
        if(ok(mid)) ub = mid;
        else lb = mid;
    }
    printf("%d\n", ub);
    return 0;
}

0になるのがコーナーケースで、lb = -1にしないとダメだった。二分探索はいつも実装でつまずいてしまう……。