UTPC2013 J K番目の閉路
問題
日本語なので本文参照(http://utpc2013.contest.atcoder.jp/tasks/utpc2013_06)
自己辺多重辺がありうる重みつき有向グラフが与えられる。
このグラフの0番の頂点から0番の頂点へ戻る閉路(同じ辺や頂点を2度使ってもよい)の長さを、
長さが短い順にK個出力せよ。
同じ長さの閉路があっても違う閉路なら違うものとしてK個の中に入れるものとする。
制約条件
頂点≦25000
辺≦10^5
K≦10^5
1≦重み≦10^9
グラフはランダムに作ったものであることが保証されている。
自己辺多重辺がありうる。
方針
よくわかってないのだけど、0番までの距離をヒューリスティック値とするA*をするだけで、ランダムグラフであれば謎の原理により計算量が落ちるらしい。
このk最短路のダイクストラは、同じ頂点に二回以上来ても探索をやめないようにする。
というわけでspaghetti sourceのk-最短路をlong longに変えてそのままコピペすれば通る。
int main(){ int n, m, k; scanf("%d%d%d", &n, &m, &k); Graph g(n); vi cost(n, (ll)1e17); vector<vector<pi> > e(n); vector<vector<pi> > re(n); rep(i, m){ int a, b, c; scanf("%d%d%d", &a, &b, &c); e[a].pb(mp(b, c)); re[b].pb(mp(a, c)); } priority_queue<pi, vector<pi>, greater<pi> > q; q.push(mp(0, 0)); cost[0] = 0; while(!q.empty()){ ll c = q.top().first; ll v = q.top().second; q.pop(); if(cost[v] < c) continue; rep(i, re[v].size()){ int to = re[v][i].first; ll nc = c + re[v][i].second; if(cost[to] > nc){ cost[to] = nc; q.push(mp(nc, to)); } } }; q.push(mp(0, 0)); while(!q.empty()){ ll c = q.top().first; ll v = q.top().second; q.pop(); if(v == 0 && c){ printf("%lld\n", c); if(--k == 0) break; } rep(i, e[v].size()){ int to = e[v][i].first; ll nc = c + e[v][i].second - cost[v] + cost[to]; q.push(mp(nc, to)); } } while(k--) puts("-1"); return 0; }