問題一覧 > 通常問題

No.1344 Typical Shortest Path Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 120
作問者 : maguromaguro / テスター : KoDKoD blackyukiblackyuki PCTprobabilityPCTprobability
5 ProblemId : 5764 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-01-18 22:28:48

問題文

N 頂点 M 辺の重み付き有向グラフ G が与えられます。G は自己ループ、負閉路を持ちません。 i(1iM) 番目の辺は頂点 si から頂点 ti に向けて張られており、重みは di です。

頂点 i からいくつかの辺を辿って到達できる各頂点 j について、頂点 i から頂点 j まで辺を辿って移動するときの辺の重みの総和の最小値を Di,j とします。ただし、 i=j または頂点 i から頂点 j にたどり着けない場合は Di,j=0 とします。

このとき、各 i (1iN) について、j=1NDi,j を求めてください。

入力

N M
s1 t1 d1
s2 t2 d2

sM tM dM

  • 入力は全て整数である。
  • 2N100
  • 1M9900
  • 1si,tiN
  • siti
  • 1012di1012
  • G は負閉路を持たない。

出力

N 行にわたって出力してください。

i (1iN) 行目には、j=1NDi,j を出力してください。 最後に改行してください。

サンプル

サンプル1
入力
4 5
3 4 3
2 1 2
4 2 6
3 1 1
1 3 1
出力
15
11
13
23

与えられたグラフは以下のようになります。

サンプル2
入力
5 7
1 2 3
2 3 4
3 1 -1
3 4 -5
3 5 -6
4 2 3
5 4 0
出力
12
3
-16
17
16

サンプル3
入力
4 6
1 2 1
1 3 -5
2 3 2
2 4 4
3 4 1
4 3 7
出力
-8
5
1
7

サンプルケースには存在しませんが、 G は多重辺を持つ可能性があります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。