ABC022 C - Blue Bird
解法
まずは想定解です。
頂点1から出るときの辺と、頂点1に帰るときの辺は違うものでなくてはなりません。
そのときの頂点をとすると、からは純粋な最短経路問題に置き換えることができます。
この問題では、頂点の個数が300までしかないので、頂点1を除いてワーシャルフロイド法を適用すると、からへの最短経路を求めることができます。
あとは、から、そしてからへの最短経路、最後にからへの距離の合計値の最小値を全探索で求めれば、最後の探索が、ワーシャルフロイド法がなので時間内に求めることができます。
コードは提出コード2です。
では、自分の解法です。
頂点1からへの経路が2つ以上ある場合、その部分は閉路になります。ということで、その2つの経路を繋ぐことで、頂点1を出て帰ってくる道を作成することができます。
ですが、このままだと同じ辺を使用する可能性があります。頂点1を出る辺と帰る辺です。ということで、頂点1から出る辺のうちどれを使用したか、を経路の距離と同時に記録しておき、被りがないようにします。
逆に、これについて考慮した時点で、その他の辺が重複することはなくなります。
というのも、行きと帰りで同じ辺を使用する経路が存在した場合、その辺を通る際に、行きと帰りで同じ頂点を通ることになります。ということは、その頂点でさっさと引き返してしまえば、現在の経路よりも短いルートを作成することができるからです。
ということで、頂点1を出た辺を記録しつつダイクストラ法を適用し、それぞれの頂点へ向かう経路が2つ以上存在していた場合に合体して答えの候補を作成、そしてその最小値を計算すれば、答えを求めることができます。
感想
制約からしてワーシャルフロイド法が使えそう、となったのですが、いい方法が思いつきませんでした。
なので、ダイクストラ法から攻めることにし、半分ごり押しのような解法を作成したため、実装にとてつもない時間がかかりました…w