ABC 401-500/ABC450B - Split Ticketing - 競技プログラミング用 知識集積所

---

問題

ABC450B

必要知識

A問題レベルのものは省略

• 二次元vector※
• 二重ループ※（この問題では三重ループ）
• 全探索※

考え方

問題通りにシミュレーションするだけ……ではあるのだが、それをするのが大変。

まず、入力が非常に特殊で、三角形状をしている。
これは、N×Nサイズの正方形の二次元vector※の一部分だけを使うとよい。
メモリが少し無駄になってしまうが、Nが最大でも100なので十分許容範囲。
i番目の駅からj番目の駅に行くコストを.at(i).at(j)でシンプルに取り出せることを優先する。

入力を受け取れたら、あとは三重ループ※で全てのパターンを全探索※すればよい。
2つ目の駅は1つ目の駅の次から、3つ目の駅は2つ目の駅の次からスタートすることで、逆行する経路を取らないようにすること。

解答例

解答例

注意点

別解