D. Buy a Ticket | Educational Codeforces #38

すべての頂点iについて
(a[i], i)を終点候補として優先順位度付きキューに突っ込んおく。
(u[i], v[i]) 間をコスト2w[i]の無向辺で接続したグラフで
ダイクストラ法っぽいことをする。

まず往復についてであるが、往路と復路の最短経路の長さが等しいことは明らか。
なので、同じ経路を往復すればいい。そのため、辺のコストを2倍して往路だけ調べればいい。

次に、なぜ終点候補から出発するかを考える。
1つの終点候補について最短の始点候補は複数存在し得る。
他方、1つの始点について最短の終点はただ1つしなかい。
前者は終点1個から、複数の始点の最短経路を計算できるため、後者より効率が良さそう。
しかも、終点候補を加えていっても問題ないし、最初にコストa[i]からスタートすれば
優先順位度付きキューで問題なく処理できる。
逆に始点から見ていくとa[i]の処理が厄介そう。