交差点 \(i, j\) の最短距離を \(D(i, j)\) とする. この距離は各頂点からの最短距離を dijkstra 法を使うことで求めておく.

トラックを交差点 \(C\) に集めるとする. そうすると, \(L\) から \(C\) に行って各交差点を回ってトラックを回収してくるときの移動距離は,

\[S = D(L, C) + 2\sum_i t_i D(C, i)\]

となる. しかし, 最初 \(C\) に行くのではなく直接トラックの元に行く方が近い場合がある. 最初に回収するトラックがいる交差点を \(F\) とすると, 移動距離は,

\[S_F = S + D(L, F) - D(L, C) - D(F, C)\]

となる.

これをすべての \(C, F\) について計算して最小値を求める.

なお, 最初から1カ所にのみトラックがある場合は移動する必要はない.