POJ 3662: Telephone Lines
概要
N頂点,辺P本のグラフが与えられる.K本の辺は無料で使うことができ,それ以上使うとK本からはみ出た辺の中での最大の長さだけの料金が発生する.
頂点1から頂点Nまでの経路をできるだけ安い料金で実現したい.
解法
料金(辺の長さの最大値)について二分探索.料金をdと仮定したとき,dより長い辺をK本以下使って1からNへの経路をつくれるかを判定する.判定にはDijkstraを利用.
typedef int Weight; struct Edge{ int from, to; Weight weight; Edge(int f, int t, Weight w) : from(f), to(t), weight(w) { } }; bool operator<(const Edge &a, const Edge &b){ return a.weight > b.weight; } typedef vector<Edge> Edges; typedef vector<Edges> Graph; const int INF = 1000000; int N, P, K; int d[1010]; bool visited[1010]; bool C(Graph &g, int L) { priority_queue<Edge> Q; for(int i = 0; i < N; ++i) d[i] = INF; memset(visited, 0, sizeof(visited)); d[0] = 0; Q.push(Edge(-1, 0, 0)); while(!Q.empty()){ int v = Q.top().to; int cnt = Q.top().weight; Q.pop(); if(visited[v]) continue; visited[v] = true; if(v == N-1) return cnt <= K; EACH(i, g[v]){ int ncnt = cnt; if(i->weight > L) ncnt++; if(d[i->to] > ncnt){ d[i->to] = ncnt; Q.push(Edge(i->from, i->to, ncnt)); } } } return false; } main(){ scanf("%d%d%d", &N, &P, &K); Graph g(N); for(int i = 0; i < P; ++i){ int a, b, l; scanf("%d%d%d", &a, &b, &l); --a; --b; g[a].push_back(Edge(a, b, l)); g[b].push_back(Edge(b, a, l)); } int lb = -1, ub = 1000010; while(ub - lb > 1){ int mid = (lb + ub) / 2; // printf(">%d\n", mid); if(C(g, mid)){ ub = mid; } else{ lb = mid; } } printf("%d\n", ub > 1000000 ? -1: ub); }