1603 Risk
問題概要
20個の国があり、それぞれの国の隣接関係が与えられる。
スタートの国からゴールの国まで辿り着くのに越えなければならない最小の国境の数を求めよ。
解法
ワーシャルフロイド。
問題が古いせいか問題文と入力が読みにくさがひどい。
ソースコード
int d[20][20]; int main(){ int a,b,c=0,T=0; while(~scanf("%d",&a)){ rep(i,20)rep(j,20)d[i][j]=i==j?0:99; rep(i,a)scanf("%d",&b),d[c][b-1]=d[b-1][c]=1; c++; for(;c<19;c++){ scanf("%d",&a); rep(i,a)scanf("%d",&b),d[c][b-1]=d[b-1][c]=1; } rep(k,20)rep(i,20)rep(j,20)d[i][j]=min(d[i][j],d[i][k]+d[k][j]); printf("Test Set #%d\n",++T); scanf("%d",&a); rep(i,a){ scanf("%d%d",&b,&c); printf("%d to %d: %d\n",b,c,d[b-1][c-1]); } puts(""); c=0; } return 0; }