PKU演習問メモ

ちょっとだけ。
今日は24:30からCodeforcesのラウンド!なんだけど体調が頗る悪いorz

2488 A Knight's Journey
p*qのチェス盤をナイトの駒が全てのマスを一度だけ通るパスのうち辞書順で最初に来るものを出力する問題。pもqも小さいので深さ優先で書けばおk.最初出力を標準エラーに出すという珍しいバグを入れてWAを貰った。
2485 Highways
最大の辺の長さが最小になるような全域木(の最大の辺の長さ)を求める問題。プリム法っぽく書いた。
2407 Relatives
n以下の自然数でnと互いに素なものの個数を求める問題。Eulerのphi関数。

2485 Highways

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		int n; scanf("%d",&n);
		int d[n][n];
		rep(i,n)rep(j,n)scanf("%d",d[i]+j);
		
		priority_queue<pi> Q; Q.push(mp(0,0));
		bool V[n]; fill(V,V+n,0);
		int nvis=0,ans=inf;
		
		while(!Q.empty())
		{
			int c=Q.top().second,mx=Q.top().first;
			Q.pop();
			
			if(V[c])continue;
			V[c]=1; nvis++;
			
			if(nvis==n)
			{
				ans=-mx; break;
			}
			
			rep(i,n)if(!V[i])
				Q.push(mp(min(mx,-d[c][i]),i));
		}
		cout<<ans<<endl;
	}
	return 0;
}