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; }