Codeforces 42 D. Strange town

問題

n個の都市があり、任意の二つの都市の間にそれらをつなぐ双方向に通行可能な道がある。
道にはそれぞれ相違なる自然数の通行料が定められている。

n個の都市を1周するとき、どのような順番で都市を巡っても、
通行料の総額が一定になる。

nが与えられたとき、上の条件を満たす通行料を1通り出力せよ。
全ての通行料は1000を超えてはならない。

制約条件

n≦20

方針

辺ごとに値dを決めてやる。
頂点iと頂点jを結ぶコストをd[i]+d[j]とすれば、
どのようにな順番で頂点を一周してもコストは同じになる。

あとは、d[i]+d[j]が全て異なるようにdを探索すればよい。
これは1から全探索して間に合う。

ソースコード

int n;
int d[20];
void rec(int c){
	if(c==n)return;
	int m=1;
	for(;;m++){
		rep(i,n)rep(j,i)rep(k,n)
		if(d[i]+d[j]==d[k]+m)goto FAIL;
		break;
		FAIL:;
	}
	d[c]=m;
	rec(c+1);
}
void run()
{
	cin>>n;
	rec(0);
	rep(i,n)rep(j,n)cout<<(i==j?0:d[i]+d[j])<<(j==n-1?"\n":" ");
}