E - Time Is Money
Darjeeling
2
s
1024
MB
400
点
問題文
TSG 国には $N$ 個の都市と $M$ 本の有料道路があります。
都市には $1$ から $N$ の番号が、道路には $1$ から $M$ の番号が振られています。
道路 $i$ は都市 $A_i$ と都市 $B_i$ を双方向に結んでいて、通行に $c_i$ 円かかりますが $t_i$ 分で到達することが出来ます。
tRue 君は都市 $1$ から都市 $N$ までなるべく早く移動したいと思っていますが、同時になるべく安く移動したいとも考えています。
tRue 君は $1$ 分に $P$ 円の価値があると考えているので、ある $2$ つの経路 $A, B$ があって、 $A$ の方が $T$ ($T > 0$ 13:24追記)分だけ早く到着できるとき、値段の差分が $P\times T$ 円以下なら、$A$ の値段が $B$ の値段より高くても $A$ を選びたいと思っています。
道路の情報と tRue 君にとっての $1$ 分の価値 $P$ 円が与えられるので、 tRue 君にとっての最善の経路の値段と時間を出力してください。
制約
- $1\le N,M\le 10^5$
- $0\le P\le 10^6$
- $1\le A_i<B_i\le N$
- $1\le c_i\le 10^6$
- $1\le t_i\le 10^3$
- 都市 $1$ から都市 $N$ まで移動できる経路は必ず存在する。
入力
入力は以下の形式で与えられる。
$N$ $M$
$P$
$A_1$ $B_1$ $c_1$ $t_1$
$\vdots$
$A_M$ $B_M$ $c_M$ $t_M$
出力
tRue 君にとって最善の経路の値段 $C$ 円と時間 $T$ 分とを空白区切りで出力してください。
$C$ $T$
入力例 1
3 3
100
1 2 300 8
2 3 200 7
1 3 1000 10
出力例 1
1000 10
都市 $2$ を通る経路よりも直接都市 $3$ へ向かう経路の方が $500$ 円高いですが $5$ 分早く到着できます。
値段の差分が $100\times 5$ 円以下なので、 tRue 君は直接都市 $3$ へ向かう方が良いです。
入力例 2
3 3
0
1 2 300 8
2 3 200 7
1 3 1000 10
出力例 2
500 15
tRue 君がお金こそが全てだと考えている場合もあります。
入力例 3
2 2
1000
1 2 1000 10
1 2 2000 5
出力例 3
2000 5
$2$ つの道路が同じ都市の組の間を結んでいる場合もあります。