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; }