Courses

アルゴリズム

順列の反復

Module: 順列の反復

Problem

4 /4

王室の旅

Problem

武兵衛 2 世国王陛下は、領内を旅したいとお考えになりました。同時に、ルートには次のような願いがあります。

1) ルートはできるだけ時間がかからないようにする必要があります (ロイヤルタイム – は非常に価値のあるものであり、保護する必要があります);

2) ルートにはすべての入植地が 1 回だけ含まれている必要があります (国王が入植地を見逃した場合、その住民は王室の不注意に激怒し、税金の支払いを停止します。国王が複数回入植地を訪れた場合、残りの入植地の住民は和解アイテムも憤慨します）

3）ルートは州の首都で始まり、終わる必要があります（彼の所有物を旅した後、王はすぐに仕事に取り掛かる必要があります）。首都はルートに 2 回含まれています。出発地としても目的地としても、ルートの途中の集落になることはできません。

王国のロードマップを使用してそのようなルートを見つけるか、すべての要件を満たすことが不可能であると判断するプログラムを作成します。

入力
最初に数値 N (自然、10 を超えない) を入力します –王国内の居住地の数。次に、各 – に N 個の数字の N 行が続きます。入植地間の移動時間 (時間 – は負でない整数で、500 を超えません。時間 = 0 の場合、これはいくつかの入植地の間に道がないことを意味します)。和解第 1 号は州都です。

インプリント
陛下が領地を迂回するのに費やす最小の合計時間を出力するか、指定されたプロパティでルートを構築することが不可能な場合は -1 を出力してください。