No.17 2つの地点に泊まりたい

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 153
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm

2 ProblemId : 61 / 出題時の順位表

問題文

\(0\)から\(N-1\)までの\(N\)個の地点がある。
地点から地点の移動コストが\(M\)個与えられる。
また各地点に滞在コストがある。

\(0\)地点から\(N-1\)地点にたどり着くまでに、 \(0\)地点と\(N-1\)地点以外の異なる\(2\)つの地点に滞在しなければならない。
滞在する地点は自由に決めて良い。
この条件での移動コストと滞在コストの合計の最小値を求めよ。

都市を通るけど、滞在しないこともできます。

入力

\(N\)
\(S_0\)
\(S_1\)
\(\dots\)
\(S_i\)
\(\dots\)
\(S_{N-1}\)
\(M\)
\(A_1\ B_1\ C_1\)
\(A_2\ B_2\ C_2\)
\(\dots\)
\(A_j\ B_j\ C_j\)
\(\dots\)
\(A_M\ B_M\ C_M\)

一行目は地点の数\(N\ (4 \leq N \leq 50)\)が与えられる。
その後の\(N\)行は\(0\)地点から\(N-1\)地点までの\(N\)個の地点の滞在コスト\(S_i\ (1 \leq S_i \leq 1000, 0 \leq i \leq N-1)\) が与えられる。
ただし、\(0\)地点と\(N-1\)地点の滞在コストは\(0\)で与えられる。

その次の行は、移動についての情報が\(M\)個 \((1 \leq M \leq N(N-1)/2)\) が与えられる。
その後の\(M\)行は移動元\(A_j\ (0 \leq A_j \leq N-1)\)、移動先\(B_j\ (0 \leq B_j \leq N-1)\)、移動コスト\(C_j\ (1 \leq C_j \leq 1000)\)の順で\(M\)個の情報が与えられる。\((1 \leq j \leq M)\)

「\(A_j\)から\(B_j\)」また「\(B_j\)から\(A_j\)」のどちらも移動可能とする。(つまり無向グラフ)
\(A_j \neq B_j\)は保証されている。
\(A_j\)から\(B_j\)(その逆も含む)への遷移は複数ないとする。

\(0\)地点から\(N-1\)地点には必ずたどり着ける経路があることが保証される。
さらに\(0\)地点と\(N-1\)地点以外の異なる\(2\)つの地点に滞在することができることが保証される。
2015/07/08 20:53追記
$0$地点から辿りつけない地点もあることに注意。

移動コストと滞在コストの単位は同一とし、加算できるものとする。

出力

移動コストと滞在コストの合計の最小値を一行で出力してください。
最後に改行してください。

サンプル

サンプル1
入力
4
0
2
100
0
5
0 1 1
0 2 1
1 2 1
1 3 1
2 3 2
出力
105

地点は全部で\(4\)個。
地点\(1\)と地点\(2\)にはかならず滞在しなけらばならない。
\(0 \rightarrow 2 \rightarrow 1 \rightarrow 3\)の順番で移動し、
地点\(1\)と地点\(2\)に滞在したとき最小コストになる。

サンプル2
入力
4
0
3
3
0
3
0 1 1
1 3 2
2 3 4
出力
17

地点\(1\)と地点\(2\)にはかならず滞在しなけらばならない。
よって、\(0 \rightarrow 1 \rightarrow 3 \rightarrow 2 \rightarrow 3\)のような移動が必要。
同じ地点を\(2\)度通っても良い。

サンプル3
入力
16
0
15
6
23
8
193
14
13
53
16
85
12
15
5
14
0
15
0 1 17
14 15 18
7 8 87
4 5 137
8 9 17
11 12 33
5 6 177
9 10 47
10 11 27
1 2 77
6 7 114
12 13 15
2 3 127
13 14 11
3 4 85
出力
1000

提出ページヘ