Einbahnstrasse (UVa Live Archive Africa and the Middle East - Africa and Arab - 2008/2009 Alexandria - Egypt)

有向グラフと壊れた車の場所が与えられる。壊れた車をトラックでガレージまで運びたい。最短経路の長さはいくらになるか。ただしトラックは最初ガレージに存在し、壊れた車は与えられた順序で運ばなければならず、一度に一台しか運べない。
頂点数<100
0<=壊れた車の数<1000
枝の数<10000

最初にフロイドワーシャルとかで距離を求めておいて、後はてきとうに計算すれば良い。