UTPC2013 J K番目の閉路

問題

日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_06）

自己辺多重辺がありうる重みつき有向グラフが与えられる。
このグラフの0番の頂点から0番の頂点へ戻る閉路（同じ辺や頂点を２度使ってもよい）の長さを、
長さが短い順に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;
}