ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC022 C - Blue Bird

問題
提出コード1
提出コード2

解法

まずは想定解です。
頂点1から出るときの辺と、頂点1に帰るときの辺は違うものでなくてはなりません。
そのときの頂点をi,jとすると、iからjは純粋な最短経路問題に置き換えることができます。
この問題では、頂点の個数が300までしかないので、頂点1を除いてワーシャルフロイド法を適用すると、iからjへの最短経路を求めることができます。
あとは、1からi、そしてiからjへの最短経路、最後にjから1への距離の合計値の最小値を全探索で求めれば、最後の探索がO(N^{2})、ワーシャルフロイド法がO(N^{3})なので時間内に求めることができます。 コードは提出コード2です。

では、自分の解法です。
頂点1からiへの経路が2つ以上ある場合、その部分は閉路になります。ということで、その2つの経路を繋ぐことで、頂点1を出て帰ってくる道を作成することができます。
ですが、このままだと同じ辺を使用する可能性があります。頂点1を出る辺と帰る辺です。ということで、頂点1から出る辺のうちどれを使用したか、を経路の距離と同時に記録しておき、被りがないようにします。
逆に、これについて考慮した時点で、その他の辺が重複することはなくなります。
というのも、行きと帰りで同じ辺を使用する経路が存在した場合、その辺を通る際に、行きと帰りで同じ頂点を通ることになります。ということは、その頂点でさっさと引き返してしまえば、現在の経路よりも短いルートを作成することができるからです。
ということで、頂点1を出た辺を記録しつつダイクストラ法を適用し、それぞれの頂点へ向かう経路が2つ以上存在していた場合に合体して答えの候補を作成、そしてその最小値を計算すれば、答えを求めることができます。

感想

制約からしてワーシャルフロイド法が使えそう、となったのですが、いい方法が思いつきませんでした。
なので、ダイクストラ法から攻めることにし、半分ごり押しのような解法を作成したため、実装にとてつもない時間がかかりました…w