ABC073 D joisino's travel
Submission #2454102 - AtCoder Beginner Contest 073
所見
見た瞬間ワーシャルフロイド+next_permutationだということは分かったが、ワーシャルフロイドをバグらせて迷宮入りした。(ありがとう: @rian_tkb)
問題概要
N個の町、M個の道、があって、道にはそれぞれコストが定義される時、N個の中からR個(R<=8)を選んだ時、R個の街をすべて訪問するのにかかる最小コストを求めよ。
取った方針
ワーシャルフロイドをするとO(N3)で全町間の最小コストが求まる。 あとはR<=8なので、next_permutationで全探索をしても十分間に合う。
正しい方針
同上
得られた知見
・全点対の最短距離を求めたい場合はワーシャルフロイドを用いる。
・ワーシャルフロイドを用いる際はループを回す変数の順番を間違えるとバグる上にほとんどのケースで正解してしまう。(一度証明を読んで理解しておくべき)
・ワーシャルフロイドを用いていて、サンプルは全部通るのに微妙にWAする場合は疑う。
・next_permutationは条件式が評価されるタイミングの問題で、do whileで使う必要がある。
解くのに必要な要素
・ワーシャルフロイド法
・順列全列挙(next_permutation)
周辺調査によって得られた知見
特になし
