D - 切符分割
解説
/
QU鉄道は、N個の駅とM個の路線を持つ鉄道会社である。
それぞれの駅には、0からN-1までの一意な駅番号が割り当てられている。
各路線は異なる2つの駅を結んでおり、どちらの方向の移動にも使うことができる。
また、QU鉄道では運賃表を使用しており、距離に応じて段階的に運賃が変わるようになっている。
ある駅Aから別の駅Bまでの切符の料金は、駅Aから駅Bまでの最短距離を元に、運賃表から決定する。
例えば、次のような路線図と運賃表を考えよう。
この例において、駅0から駅6までの運賃を考えよう。
駅0から駅6までの距離は合計で41kmであるから、 運賃表より、駅0から駅6までの切符は740円となる。
QU鉄道では、区間の異なる複数の切符を使って、ある駅から別の駅へ移動することもできる。
これを切符分割と呼ぶことにする。
例えば、次の2つの切符を持っていれば、駅0から駅6まで移動することができる。
このように、QU鉄道では、切符分割により運賃が安くなる場合が存在する。
さらに、次のように3枚の切符を使って、駅0から駅6まで移動する場合を考える。
倹約家の胡桃さんは、このような切符分割をうまく使うことで、交通費を節約しようと考えた。
胡桃さんは、駅Sから駅Gへ行きたいが、もし可能であれば、切符分割により運賃を安く済ませたい。
しかしながら、切符を何枚も買うのは、胡桃さんにとって面倒である。
そこで胡桃さんは、最大2枚の切符を使って、駅Sから駅Gへ移動しようと考えた。
したがって、上記の例において、胡桃さんが駅0から駅6まで移動する場合には、710円が必要となる。
あなたの仕事は、胡桃さんが駅Sから駅Gへ移動するために必要な交通費の最小値を求めることである。
入力は以下の形式で与えられる。
入力中の各変数はすべて整数である。また、以下の制約を満たす。
切符を最大2枚購入するときの、駅Sから駅Gへの運賃の合計の最小値を、1行に出力せよ。出力の末尾には改行を入れなければならない。
以下の3つの制約を満たすテストケースに正答すると、20点を得ることができる。
以下の2つの制約を満たすテストケースに正答すると、20点を得ることができる。
実行時間制限: 4 sec / メモリ制限: 256 MB
問題文
それぞれの駅には、0からN-1までの一意な駅番号が割り当てられている。
各路線は異なる2つの駅を結んでおり、どちらの方向の移動にも使うことができる。
また、QU鉄道では運賃表を使用しており、距離に応じて段階的に運賃が変わるようになっている。
ある駅Aから別の駅Bまでの切符の料金は、駅Aから駅Bまでの最短距離を元に、運賃表から決定する。
例えば、次のような路線図と運賃表を考えよう。
距離 | 運賃 |
---|---|
1 km - 6 km | 180 円 |
7 km - 15 km | 230 円 |
16 km - 25 km | 400 円 |
26 km - 40 km | 530 円 |
41 km - 60 km | 740 円 |
61 km以上 | 820 円 |
この例において、駅0から駅6までの運賃を考えよう。
駅0から駅6までの距離は合計で41kmであるから、 運賃表より、駅0から駅6までの切符は740円となる。
QU鉄道では、区間の異なる複数の切符を使って、ある駅から別の駅へ移動することもできる。
これを切符分割と呼ぶことにする。
例えば、次の2つの切符を持っていれば、駅0から駅6まで移動することができる。
- 駅0から駅1までの切符: 6km、180円
- 駅1から駅6までの切符: 35km、530円
このように、QU鉄道では、切符分割により運賃が安くなる場合が存在する。
さらに、次のように3枚の切符を使って、駅0から駅6まで移動する場合を考える。
- 駅0から駅2までの切符: 13km、230円
- 駅2から駅4までの切符: 14km、230円
- 駅4から駅6までの切符: 14km、230円
倹約家の胡桃さんは、このような切符分割をうまく使うことで、交通費を節約しようと考えた。
胡桃さんは、駅Sから駅Gへ行きたいが、もし可能であれば、切符分割により運賃を安く済ませたい。
しかしながら、切符を何枚も買うのは、胡桃さんにとって面倒である。
そこで胡桃さんは、最大2枚の切符を使って、駅Sから駅Gへ移動しようと考えた。
したがって、上記の例において、胡桃さんが駅0から駅6まで移動する場合には、710円が必要となる。
あなたの仕事は、胡桃さんが駅Sから駅Gへ移動するために必要な交通費の最小値を求めることである。
入力
N M K S G a_0 b_0 d_0 a_1 b_1 d_1 : a_{M-1} b_{M-1} d_{M-1} x_0 f_0 x_1 f_1 : x_{K-1} f_{K-1}
- 1行目には、駅の数N、路線の数M、運賃表のサイズKが与えられる。
- 2行目には、出発駅の番号S、到着駅の番号Gが与えられる。
- 3行目からM+2行目には、路線の情報が与えられる。各行は、駅a_iとb_iを結ぶ、距離d_iの路線が存在することを表す。
- M+3行目からM+K+2行目には、運賃表の情報が与えられる。任意のj\ (0≦j<K)および距離l\ (l≧1)について、x_j≦l<x_{j+1}を満たすならば、距離lに対する運賃がf_jであることを表す。ただし、x_Kは無限大であると仮定する。
制約
- 2≦N≦30000
- 1≦M≦60000
- 1≦K≦100
- 0≦S<N
- 0≦G<N
- S≠G
- 任意の0≦i<Mに対し、0≦a_i<N,\ 0≦b_i<N,\ a_i≠b_i
- 任意の0≦i<j<Mに対し、\{a_i,b_i\}≠\{a_j,b_j\}
- 任意の0≦i<Mに対し、1≦d_i≦10^4
- 1=x_0<x_1<...<x_{K-1}≦10^9
- 1≦f_0<f_1<...<f_{K-1}≦10^9
- 駅Sから駅Gへの経路が存在する
出力
部分点 1
- 2≦N≦100
- 1≦M≦200
- 切符分割により交通費が安くなることはない。 すなわち、駅Sから駅Gまでの切符1枚のみを購入するのが最適となる。
部分点 2
- 2≦N≦100
- 1≦M≦200
入力例 1
7 6 6 0 6 0 1 6 1 2 7 2 3 6 3 4 8 4 5 5 5 6 9 1 180 7 230 16 400 26 530 41 740 61 820
出力例 1
710
- 問題文中に示した通りである。
入力例 2
7 6 6 4 1 0 1 6 1 2 7 2 3 6 3 4 8 4 5 5 5 6 9 1 180 7 230 16 400 26 530 41 740 61 820
出力例 2
400
- 入力例1と路線および運賃表は同じであるが、出発駅および到着駅が異なる。この場合は、駅4から1までの切符をそのまま買ったほうが良い。
入力例 3
5 5 4 0 4 0 1 2 1 2 3 2 4 5 1 3 8 3 4 6 1 100 4 200 9 400 16 600
出力例 3
300
- ある駅から別の駅への経路は、複数存在することもある。
入力例 4
2 1 2 0 1 0 1 3 1 100 3 210
出力例 3
210