ABC 401-500/ABC411B - Distance Table - 競技プログラミング用 知識集積所

---

問題

ABC411B

必要知識

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

• 二重ループ（未作成）（というか三重ループ）
• 二次元vector（未作成）（使用を避けることもできる）

考え方

「どの駅からどの駅から」の組み合わせすべてについて、簡単な問題を解いていくだけ。
組み合わせの列挙は二重ループ（未作成）で実現でき、それぞれの問題も単純なforループで解ける。
問題は、これをどうやって保持し、どうやって出力するか。

二次元vector（未作成）は多くの場合長方形的なサイズを持つ。
しかし今回出力したいものはそうではない。
そこで、空のvector（未作成）をn-1個並べたものを用意し、代入ではなくemplace_back()でデータを入れていくとよい。
また、出力は、forループの終了判定を.size()で行うとよい。

あるいは、二次元vector（未作成）に入れるのではなく、空白か改行かをうまく切り替えながら直接出力してもよい。

解答例

解答例

注意点

別解

累積和を使う

累積和を使うことで、高速に処理できる。
とはいえ、B問題なので高速化する意味も特にないのだが……。
解答例