D - 切符分割

Time Limit: 4 sec / Memory Limit: 256 MB

問題文

QU鉄道は、N個の駅とM個の路線を持つ鉄道会社である。
それぞれの駅には、0からN-1までの一意な駅番号が割り当てられている。
各路線は異なる2つの駅を結んでおり、どちらの方向の移動にも使うことができる。
また、QU鉄道では運賃表を使用しており、距離に応じて段階的に運賃が変わるようになっている。
ある駅Aから別の駅Bまでの切符の料金は、駅Aから駅Bまでの最短距離を元に、運賃表から決定する。

例えば、次のような路線図と運賃表を考えよう。
距離運賃
1 km - 6 km180
7 km - 15 km230
16 km - 25 km400
26 km - 40 km530
41 km - 60 km740
61 km以上820

この例において、駅0から駅6までの運賃を考えよう。
0から駅6までの距離は合計で41kmであるから、 運賃表より、駅0から駅6までの切符は740円となる。

QU鉄道では、区間の異なる複数の切符を使って、ある駅から別の駅へ移動することもできる。
これを切符分割と呼ぶことにする。
例えば、次の2つの切符を持っていれば、駅0から駅6まで移動することができる。
  • 0から駅1までの切符: 6km、180
  • 1から駅6までの切符: 35km、530
このときの運賃の合計は180+530=710円となり、 駅0から駅6までの切符1枚を買う場合と比べて安くなる。
このように、QU鉄道では、切符分割により運賃が安くなる場合が存在する。

さらに、次のように3枚の切符を使って、駅0から駅6まで移動する場合を考える。
  • 0から駅2までの切符: 13km、230
  • 2から駅4までの切符: 14km、230
  • 4から駅6までの切符: 14km、230
このときの運賃の合計は230+230+230=690円となり、さらに安くなる。

倹約家の胡桃さんは、このような切符分割をうまく使うことで、交通費を節約しようと考えた。
胡桃さんは、駅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_ib_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への経路が存在する

出力

切符を最大2枚購入するときの、駅Sから駅Gへの運賃の合計の最小値を、1行に出力せよ。出力の末尾には改行を入れなければならない。

部分点 1

以下の3つの制約を満たすテストケースに正答すると、20点を得ることができる。
  • 2≦N≦100
  • 1≦M≦200
  • 切符分割により交通費が安くなることはない。 すなわち、駅Sから駅Gまでの切符1枚のみを購入するのが最適となる。

部分点 2

以下の2つの制約を満たすテストケースに正答すると、20点を得ることができる。
  • 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