>>316
python(pypy)　https://ideone.com/DV1w4s

本線： キュー使用したダイクストラ (+ 経路復元)。

サンプル程度なら、ワーシャルフロイド(頂点^3)でも回る、と同方も追加。
さすがにpythonには少々きつく、pypyに逃げた。