けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

前処理: Floyd-Warshall法

AtCoder ABC 073 D - joisino's travel (400 点)

Floyd-Warshall で前処理してどうのこうのする問題。特に ICPC 系などでよくある! 問題へのリンク 問題概要 頂点 辺の重み付き無向グラフが与えられる。このグラフ上で 個のチェックポイントをなす頂点集合が指定されている。好きなチェックポイントからス…

AtCoder ABC 051 D - Candidates of No Shortest Paths (400 点) 〜 3 通りの解法 〜

「最短路として選ばれる可能性がないところを挙げる」というのは、それ自体、高難易度問題で部分的に必要になる考察だったりするね。 問題へのリンク より高難易度な問題の部分問題となる例として、 RUPC 2018 day3-F 最短距離を伸ばすえびちゃん がある。こ…

AOJ 2200 Mr. リトー郵便局 (ICPC 模擬国内 2010 D)

問題文長い... 問題へのリンク 問題概要 頂点、 辺の重み付き無向グラフが与えられる。各辺は「陸路」「海路」の属性がある。このグラフを、最初頂点 にいて、 の順番に最短時間で巡りたい (順番的に後の頂点を先に通ってもよいが、その頂点より前の指定頂点…