atcoder_水色精進記録5_ABC073d

Atcoder水色精進記録

ABC073
D - joisino's travel
https://atcoder.jp/contests/abc073/tasks/abc073_d

アルゴリズム・データ構造

ワーシャルフロイド・順列全探索

考察

最初と最後を自由に決められるサラリーマン循環問題？
N＝200
R =max(8)

R=max(8)のため、順列全探索が可能？
8!=40,320 → Yes

全探索中に各都市の距離を求めるのは計算量が大きくなるため事前に距離を求めておく。
ワーシャルフロイドで全ての頂点間の最短経路を求める。
N**3 = 200200200=8,000,000なので可能。

ワーシャルフロイドでの最短経路で既に通った街を経由する場合がある？
その場合、順列全探索で最小にならないため気にしなくてOK

提出

感想

ワーシャルフロイドを自分で実装出来た。