トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

AtCoder Beginner Contest 073

[競技プログラミング,競プロ解説]

AtCoder Beginer Contest 073 - D

  解説

問題文

 Atcoder国には N 個の町があり、
 M 本の双方向に移動可能な道で結ばれています。
 
 また、 
 
 i 本目の道は町 
 Ai と町 
 Bi の間を距離 
 Ci で結んでいます。

道とか距離というキーワードで グラフアルゴリズム の問題だと見当がつく。

 joisinoお姉ちゃんは、この国の 
 R 個の町 r1,r2..rR を訪れることとなりました。
 
 最初に訪れる町までの移動と、最後に訪れる町からの移動は空路で行うが、それ以外は道を使わなければなりません。
 
 町を訪れる順番を、道での移動距離が最小となるように決めた時の移動距離を答えてください。

joisinoお姉ちゃんって誰なんだ?これで思いつく道筋は

  1. 各町~町への最小距離を全て求める(全点対最短経路問題)
  2. R 個の町 r1,r2..rR を並び替えて全列挙する(順列)
  3. 全列挙したときのそれぞれの距離を出して最小値を出す

でいけそう

各町~町への最小距離を全て求める(全点対最短経路問題)

  • ワーシャルフロイド法 やるだけ、やったぜ
    • と、思うじゃん?
    • まともにワーシャルフロイドするとLL言語では通りません

R 個の町 r1,r2..rR を並び替えて全列挙する(順列)

  • Rの最大値が8以下なので通ります

全列挙したときのそれぞれの距離を出して最小値を出す

  • 自明

https://wandbox.org/permlink/8PSgHGNvjOWOlXmu

お名前: コメント: