AOJ 2005 - Water Pipe Construction

問題
提出コード

解法

設置コストを辺の距離とみなすと、結局何かしらの距離の最小値を求めるような問題に帰着できそうな気がします。ここで、制約に注目すると、が100以下であり、[tex:O(N³)]が通ることから、ワーシャルフロイド法が使えそう、ということがわかります。
さて、問題の条件を満たすための条件は、から、からに向かう経路が存在することで、これらの経路の距離の総和が最小になればよいです。
ここで、上の経路に含まれる以外の辺は絶対に使わないので、以下のような2パターンのみに限定できます。

1つめは、図の左側のような、どこかの頂点までは、共に同じ経路をたどり、で分岐するようなパターンです。
2つめは、図の右側のような、の経路の途中にそもそもが含まれているパターンです(もちろん、とが逆でもよいです)。しかし、これは、からの距離を0とみなしてしまえば、と分岐点が一致したとみなすことができます。

ということで、あとはありうる分岐点が通りあるので、それぞれについて、の距離の総和を求め、その最小値を取ればよいです(もちろん、そもそも経路が存在しなければ無視します)。

感想

解法のポイントに気づいて注目すると、考察がすぐに終わるパターンですね。今回は、分岐点と、制約のの部分でした。
350点問題でもこのような問題があるので、サクサクといていきたいですね。