POJ-3662 : Telephone Line

問題概要

重み付き無向グラフが与えられる。0からN-1までの経路のうちK+1番目に大きい値を最小化したい。最小値を求める問題。

解法

解について二分探索する。判定関数は、コストx以上なら1、それ以外なら0を重みとして0からN-1までの最短路がK以下になるかどうか、とすればよい。辺のコストには重複があるので、「以上」でないと間違う。
また、0-1の最短路なのでdequeを使うことで計算量を落とせる。

acceptされたコード

#include <cstdio>
#include <algorithm>
#include <deque>
#include <vector>
using namespace std;

const int MAX_N = 1000;
const int MAX_C = (int)(1e6);
const int INF = 1<<29;

typedef int cost_t;

struct edge {
	int tar;
	cost_t cost;

	edge(){}
	edge(int tar, cost_t cost):
		tar(tar), cost(cost)
	{}
};

struct state {
	cost_t dist;
	int vert;
	state(){}
	state(int vert, cost_t dist):
		vert(vert), dist(dist)
	{}
};

int N, M, K;
vector<edge> graph[MAX_N];
cost_t dist[MAX_N];

cost_t dijkstra(int from, int to, int x) {
	fill(dist, dist + N, INF);

	deque<state> que;
	dist[from] = 0;
	que.push_back(state(from, 0));

	for (; !que.empty();) {
		state tp = que.front(); que.pop_front();
		int v = tp.vert;
		cost_t d = tp.dist;
		if (dist[v] < d) {
			continue;
		}

		for (int i = 0; i < (int)graph[v].size(); ++i) {
			const int u = graph[v][i].tar;
			cost_t nd = d + (graph[v][i].cost >= x ? 1 : 0);
			if (dist[u] > nd) {
				dist[u] = nd;
				if (d == nd) {
					que.push_front(state(u, nd));
				}
				else {
					que.push_back(state(u, nd));
				}
			}
		}
	}

	return dist[to];
}

void init() {
	scanf("%d%d%d", &N, &M, &K);
	for (int _ = 0; _ < M; ++_) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		--x; --y;
		graph[x].push_back(edge(y, z));
		graph[y].push_back(edge(x, z));
	}
}

int solve() {
	int low = 0, high = MAX_C + 2;

	for (;high - low > 1;) {
		int mid = (high + low) / 2;
		if (dijkstra(0, N-1, mid) > K) {
			low = mid;
		}
		else {
			high = mid;
		}
	}

	return low > MAX_C ? -1 : low;
}

int main(){
	init();
	printf("%d\n", solve());

	return 0;
}