레이팅 미적용定期券を購入する際に指定する経路をうまく選んだときの,駅U から駅V への移動にかかる運賃の最小
値を求めるプログラムを作成せよ.
小課題1 [16 点]
• S = U を満たす.
小課題2 [15 点]
• 駅S から駅T へ最小の運賃で移動するときに用いることができる経路は1 通りしかない.
小課題3 [24 点]
• N ≦300 を満たす.
小課題4 [45 点]
• 追加の制限はない.
標準入力から以下の入力を読み込め.
• 1 行目には,2 個の整数N, M が書かれている.これらは,JOI 君が住む都市にN 個の駅とM 本の鉄
道路線があることを表す.
• 2 行目には,2 個の整数S, T が書かれている.これらは,JOI 君が駅S から駅T への定期券を購入
することを表す.
• 3 行目には,2 個の整数U, V が書かれている.これらは,JOI 君が駅U から駅V への移動にかかる
運賃を最小化したいことを表す.
• 続くM 行のうちのi 行目(1 ≦i ≦M) には,3 個の整数Ai, Bi,Ci が書かれている.これらは,鉄道路
線i が駅Ai と駅Bi を双方向に結び,その運賃がCi 円であることを表す.
第17 回日本情報オリンピック(JOI 2017/2018) 本選
2018 年2 月11 日(茨城県つくば市)
標準出力に,定期券を購入する際に駅S から駅T への経路をうまく指定したときの,駅U から駅V へ
の移動にかかる運賃の最小値を1 行で出力せよ.
制限
すべての入力データは以下の条件を満たす.
• 2 ≦N ≦100 000.
• 1 ≦M ≦200 000.
• 1 ≦S ≦N.
• 1 ≦T ≦N.
• 1 ≦U ≦N.
• 1 ≦V ≦N.
• S , T.
• U , V.
• S , U またはT , V.
• どの駅から他のどの駅へも1 本以上の鉄道路線を用いて到達できる.
• 1 ≦Ai < Bi ≦N (1 ≦i ≦M).
• 1 ≦i < j ≦M に対し,Ai , A j またはBi , Bj.
• 1 ≦Ci ≦1 000 000 000 (1 ≦i ≦M).
第17 回日本情報オリンピック(JOI 2017/2018) 本選
2018 年2 月11 日(茨城県つくば市)
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1
2
6 5
1 2
3 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
3000000000
8 8
5 7
6 8
1 2 2
2 3 3
3 4 4
1 4 1
1 5 5
2 6 6
3 7 7
4 8 8
15
5 5
1 5
2 3
1 2 1
2 3 10
2 4 10
3 5 10
4 5 10
0
10 15
6 8
7 9
2 7 12
8 10 17
1 3 1
3 8 14
5 7 15
2 3 7
1 10 14
3 6 12
1 5 10
8 9 1
2 9 7
1 4 1
1 8 1
2 4 7
5 6 16
19