UTPC 2013 : J - K番目の閉路

む、これまた自力では思いつかない解法…。
http://utpc2013.contest.atcoder.jp/tasks/utpc2013_10

問題

N頂点・M有向辺の距離付きグラフが与えられる。
0番の点から始め0番の点に戻る閉路の長さを小さい順にK個求めよ。

なお、グラフの形状は乱数で生成される。

解法

Dijkstraで0に戻る点をK通りまで列挙するとTLEする。

以下の２段階で処理を行うとよい。

• 有向辺を逆向きにすることで、各頂点から0番に戻る最小コストをDijkstraで求める。
• 元の有向辺で、(0からの総移動距離 + さっき求めた0番に戻る最少コスト)が小さくなる順にA*で探索し、0番に戻る最小コストをK個まで求める。

いきなりDijkstraで探索せず、0番に戻る最少コストを加算して探索することで計算量を落とすことができる。
意図的に意地悪な形状のグラフを作るとこれでもTLEするが、乱数で生成したグラフのため各点の辺の次数が少なく、計算時間はコンパクトに収まる。
詳細はEditorial参照。

int N,M,K;
vector<pair<int,int> > E[100001],RE[100001];
ll D[100001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>K;
	FOR(i,M) {
		cin>>x>>y>>j;
		E[x].push_back(make_pair(y,j));
		RE[y].push_back(make_pair(x,j));
	}
	FOR(i,N) D[i]=1LL<<50;
	D[0]=0;
	
	set<pair<ll,int> > S;
	S.insert(make_pair(0,0));
	j=0;
	while(!S.empty()) {
		pair<ll,int> k=*S.begin();
		j++;
		x=k.second;
		S.erase(S.begin());
		if(D[x]!=k.first) continue;
		
		FOR(i,RE[x].size()) {
			int tar=RE[x][i].first;
			if(D[tar]>D[x]+RE[x][i].second) {
				D[tar]=D[x]+RE[x][i].second;
				S.insert(make_pair(D[tar],tar));
			}
		}
	}
	
	priority_queue<pair<ll,int>, vector<pair<ll,int> >, greater<pair<ll,int> > > Q;
	Q.push(make_pair(0,0));
	while(!Q.empty()) {
		ll co=Q.top().first;
		int cur=Q.top().second;
		Q.pop();
		
		if(co > 0 && cur==0) {
			_P("%lld\n",co);
			if(--K==0) break;
		}
		
		FOR(i,E[cur].size()) {
			int tar=E[cur][i].first;
			Q.push(make_pair(co-D[cur]+E[cur][i].second+D[tar],tar));
		}
	}
	
	while(K--) _P("-1\n");
}

まとめ

こういうのは思い浮かばないな…。
ほんとUTPCは難しいグラフ問題が多い。