E - 全点対最短経路問題 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

N個の街があり、0, 1, 2, ..., N-1と番号がついています。また、M本の道があり、0, 1, 2, ..., M-1と番号がついています。

道iは街u_iから街v_iへの一方通行の道で、通るのにc_i分かかります。どの街からも、他の任意の街へ到達できることがわかっています。

全ての (i, j) (0 \leq i, j \lt N) の組について、街iから街jまで移動するのに必要な時間の最小値を求め、その合計値を出力してください。

制約

  • 入力は全て整数である
  • 2 \leq N \leq 100
  • 1 \leq M \leq 10^5
  • 0 \leq u_i, v_i \lt N (0 \leq i \lt M)
  • u_i \neq v_i (0 \leq i \lt M)
  • (u_i,v_i)\neq (u_j, v_j) (i \neq j)
  • 0 \leq c_i \leq 10^9 (0 \leq i \lt M)
  • どの街からも他の任意の街へ到達できる

入力

入力は以下の形式で標準入力から与えられる。

N M
u_0 v_0 c_0
u_1 v_1 c_1
:
u_{M-1} v_{M-1} c_{M-1}

出力

街iから街jまで移動するために必要な時間の最小値を、全ての (i, j) (0 \leq i, j \lt N) の組について求め、その合計値を出力せよ。

入力例 1

3 4
0 1 1
1 0 2
1 2 3
2 0 4

出力例 1

19

与えられる入力は下図のようになっています。

例

  • 街0から街1へは1分で移動できます。
  • 街0から街2へは4分で移動できます。
  • 街1から街0へは2分で移動できます。
  • 街1から街2へは3分で移動できます。
  • 街2から街0へは4分で移動できます。
  • 街2から街0へは5分で移動できます。

よって合計で19分となります。