ストーリー
緑色の龍(?)「この宇宙に散らばったN個の玉を全て揃えれば好きな願いを叶えてやろう」
あなたは地球人であり,この宇宙に広がる星を旅して,N箇所に散らばった玉を全て集めて再び地球に戻りたい.
宇宙には高い戦闘力を持つ宇宙人がたくさん居るので戦闘力の低い地球人が通れる経路は限られている.
また,星間の移動にはc光年かかってしまうので寿命が短い地球人はなるべく早く旅を終わらせたい.
そこであなたは旅の計画を立てる為にN個の玉を全て集めて再び地球に戻る時にかかる最短経路とそのコストを知りたい.
問題
ノード数Vと,ノード間の経路数Eの有向グラフが与えられる.
ノードには1~Vまでの番号が付けられている.
また,各経路にはcaiとcbiが与えられる.
それぞれcaiはaからbに向かうコスト,cbiはbからaに向かうコストである.
さらに通るべき地点数Nとスタート地点Sが与えられ,その後指定されるN箇所を全て通って再びSに戻る.
この時の最短経路とそのコストを求めよ.
なお,複数の経路が考えられる場合はそのうちのいずれか1つを表示すれば良い.
また,辿り着くことが出来ない場合は -1 を表示せよ.
入力
V E
a1 b1 ca1 cb1
. . . .
. . . .
. . . .
aE bE caE cbE
N S
p1
.
.
.
pN
1行目にノード数Vと経路数Eが与えられる.
2行目からE+1行目にa,bを結ぶコストcaiとb,aを結ぶコストcbiが与えられる.
E+2行目に通るべき地点数Nとスタート地点Sが与えられる.
E+3行目からE+N+3行目に通るべき地点piが与えられる.
出力
Sから出発し,N箇所を周る最短経路とそのコストを出力せよ.
1行目に最小コストを出力し,2行目に経路(通ったノード番号)を空白区切りで出力する.
2行目の最後には空白を含まないこと,更に出力の背後には改行を入れること.
※なお,複数の経路が考えられる場合はそのうちのいずれか1つを表示すれば良い.
※また,辿り着くことが出来ない場合は -1 を表示せよ.
(大事な事なので2度ry…)
制約
全ての入出力ケースについて以下を満たす.
- 10 ≦ V ≦ 300
- 10 ≦ E ≦ 104
- 0 ≦ a, b, S, pi ≦ V
- 0 ≦ cai, cbi ≦ 100
- 3 ≦ N ≦ 15
入出力例
入力例1
6 8 1 2 2 2 1 3 4 3 1 4 4 2 2 5 3 2 3 4 4 2 3 6 1 2 4 6 1 1 5 6 1 2 5 1 2 3 4 5 6
出力例1
1 2 5 6 4 3 1 12
解説
このグラフを図にすると下記のようになる.
このグラフは
Path: 1 -> 2 (Cost: 2)
Path: 2 -> 5 (Cost: 3)
Path: 5 -> 6 (Cost: 1)
Path: 6 -> 4 (Cost: 1)
Path: 4 -> 3 (Cost: 2)
Path: 3 -> 1 (Cost: 3)
入力例2
6 8 1 2 2 2 1 3 4 3 1 4 4 2 2 5 3 2 3 4 4 2 3 6 1 2 4 6 1 1 5 6 1 2 2 1 5 4
出力例2
1 2 5 6 4 1 9
解説
入力例1と同じグラフであるが通るべき地点は4, 5の2箇所で良い.
したがって次のような経路になる.
Path: 1 -> 2 -> 5 (Cost: 5)
Path: 5 -> 6 -> 4 (Cost: 2)
Path: 4 -> 1 (Cost: 2)
入力例3
6 7 1 2 2 2 1 3 4 3 1 4 4 2 2 5 3 2 3 4 4 2 3 6 1 2 4 6 1 1 2 1 5 4
出力例3
1 4 1 2 5 2 1 15
解説
5-6間をつなぐ経路が無いグラフでは次のようになる.
Path: 1 -> 4 (Cost: 4)
Path: 4 -> 1 -> 2 -> 5 (Cost: 7)
Path: 5 -> 2 -> 1 (Cost: 4)
入力例4
6 6 1 2 2 2 1 3 4 3 1 4 4 2 3 4 4 2 3 6 1 2 4 6 1 1 2 1 5 4
出力例4
-1
解説
地点5に行く経路が全くない.
あなたの願いが叶うことは無かった.(涙目)
追記: 作問者は卒業生です.解説等行うのが難しいので分からなかったらei1333とかei1417とか強そうな人に聞いてどうぞ.