yukicoder : No.160 最短経路のうち辞書順最小

割と典型な問題。
本番バグのあるコードでACしたが、コンテスト後リジャッジにより0pt…。
http://yukicoder.me/problems/417

問題

N頂点M辺のグラフが与えられる。
各辺は無向辺であり、正の移動コストが設定されている。

頂点Sから頂点Gに至る最小コスト経路のうち、経由する頂点順が辞書順最小となるものを答えよ。

解法

Nが最大200と小さいので、まずWarshall-Floyed法などで全頂点間の最小移動コストを求める。
以下頂点x,y間の最小移動コストをD(x,y)と書く。

現在いる頂点xから次に移動するyを求めたい。
辞書順最小の並びを求める典型手法として、yを番号の近い順に探索し、以下の条件を満たす最小のyに移動する。

• xとyの間に辺がある。
• yがx→Gの最小コスト経路上で有りうる。すなわちD(x,y)+D(y,G)==D(x,G)を満たす。

int N,M,S,G;
int mat[300][300];
int mat2[300][300];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>S>>G;
	FOR(x,300) FOR(y,300) mat[x][y]=1<<25;
	FOR(x,300) mat[x][x]=0;
	FOR(i,M) {
		cin>>x>>y>>r;
		mat[x][y]=mat[y][x]=r;
		mat2[x][y]=mat2[y][x]=r;
	}
	FOR(i,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][i]+mat[i][y]);
	
	_P("%d",S);
	while(S!=G) {
		FOR(i,N) if(mat2[S][i]+mat[i][G]==mat[S][G] && mat2[S][i]) break;
		_P(" %d",S=i);
	}
	_P("\n");
}

まとめ

yukicoderは末尾の空白を無視してくれないので、ちょっと出力がめんどい。
codeforcesはそこらへん手抜きして出力しても平気なんだけどな。