POJ 3662 Telephone Lines

解法

二分探索 + bfs
自分で支払う上限で二分探索する
判定方法は上限より大きい辺のコストを1、上限以下の辺のコストを0としたグラフ上でbfs
コストk以下で到達できればok

const int inf = ten(9);
int n, p, k;
vector<pint> e[1024];
bool bfs(int pay_upper)
{
    int cost[1024]; // num free uses
    fill(cost, cost + n, inf);
    deque<int> q;
    cost[0] = 0;
    q.push_back(0);
    while (!q.empty())
    {
	int v = q.front();
	q.pop_front();
	int c = cost[v];

	if (c > k)
	    return false;
	if (v == n - 1)
	    return true;

	for (int i = 0; i < e[v].size(); ++i)
	{
	    int l = e[v][i].first;
	    int to = e[v][i].second;

	    if (l <= pay_upper)
	    {
		if (c < cost[to])
		{
		    cost[to] = c;
		    q.push_front(to);
		}
	    }
	    else
	    {
		if (c + 1 < cost[to])
		{
		    cost[to] = c + 1;
		    q.push_back(to);
		}
	    }
	}
    }
    return false;
}
int main()
{
    scanf("%d%d%d", &n, &p, &k);
    vector<int> len;
    while (p--)
    {
	int u, v, l;
	scanf("%d%d%d", &u, &v, &l);
	--u, --v;
	e[u].pb(pint(l, v));
	e[v].pb(pint(l, u));
	len.pb(l);
    }
    len.pb(0);
    uniq(len);

    int low = -1, high = len.size();
    while (high - low > 1)
    {
	int mid = (low + high) / 2;
	if (bfs(len[mid]))
	    high = mid;
	else
	    low = mid;
    }
    int res = high == len.size() ? -1 : len[high];
    printf("%d\n", res);
}