解答:Submission #25886274 - AtCoder Beginner Contest 218
解法:各辺を除いて逐一最短経路の算出をやると、辺の数がN2のオーダーなので、例えばダイクストラならO(N3logN)で間に合わないっぽい。
ここで一つ最短経路が見つかったとする。すると最短経路以外の辺は除いても最短経路を通れるのでその最短経路の長さを返せばよい。最短経路上の辺は愚直に最短経路の算出をやることになるが、最短経路は最長でN-1であるため、O(NlogN + N2logN)で間に合う。