ABC245 G - Foreign Friends (600)
コンテスト中の考察
全ての人、国について状態を持つのは状態数が多くて不可能
それぞれの点について自身の国からの距離とそれ以外からの距離を持てば良いのではと考えた
他の国についても区別する必要があった
人気者からその国の人同士を繋ぐ辺だけで最小距離を求める
それぞれの人から別の国への最小距離を求める
これらを使って最小距離と人気者への距離から別の国の人気者へ最小距離を求める
自国の人気者へ自国の辺だけで繋がっているとは限らない
この結果が別の結果の最短距離に含まれるかもしれないが求める順番が分からない
解説の方法
それぞれの人気者からのダイクストラ法を同時に行う
それぞれについて自分の国を始点とした場合の距離を0として優先度付きキューにも追加する
国毎の距離は二つ持っていれば良い
少なくてもどちらかは自分の国とは異なるため
あとは各点の距離を2つしか持てないように制限してダイクストラ法をすれば良い
最後のコストを求める際に注意
片方だけが違う国であればそれの結果を使えば良い
両方違う国の場合は小さい方の値を使う必要がある