1. paizaラーニングトップ
  2. レベルアップ問題集
  3. DAG・メモ化再帰メニュー(言語選択)
  4. 問題一覧 Java編
  5. 木上の最短経路 Java編

DAG・メモ化再帰メニューのサムネイル
木上の最短経路 Java編(paizaランク B 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!

問題

下記の問題をプログラミングしてみよう!

N 頂点からなる木が与えられます。 N - 1 個の辺について、 i 番目の辺は頂点 S_i と頂点 T_i をつないでおり、その距離は D_i です。あなたは現在、木の根である頂点 1 にいます。

ノード 1 から各ノードへの最短距離をそれぞれ求めてください。

入力される値

N
S_1 T_1 D_1
S_2 T_2 D_2
...
S_{N-1} T_{N-1} D_{N-1}


・ 1 行目に、木の頂点の数が与えられます。
・ 2 行目から N 行目にかけて、辺が与えられます。


入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
期待する出力

i 行目の出力では頂点 1 から頂点 i への最短距離を出力してください。

また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ N ≦ 100,000
・ 1 ≦ S_i, T_i ≦ N
・ 1 ≦ D_i ≦ 100,000

入力例1

6
1 2 3
1 3 1
2 4 2
2 5 1
3 6 1

出力例1

0
3
1
5
4
2

問題一覧へ戻る

ページの先頭へ戻る