Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 6 点
問題文
N 階建てのビルがあり、階段と M 台の直通エレベーターが設置されています。
階段を用いると、任意の i \, (1 \leq i \leq N - 1) について、i 階と i+1 階の間を双方向に 1 分で移動することができます。
また、各 i \, (1 \leq i \leq M) について、i 台目のエレベーターを用いると、A_i 階と B_i 階の間を双方向に C_i 分で移動することができます。
1 階から N 階まで移動するために最短で何分かかるか求めてください。
制約
- 2 \leq N \leq 10^{18}
- 1 \leq M \leq 10^5
- 1 \leq A_i \lt B_i \leq N
- 1 \leq C_i \leq 10^{18}
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 C_1 \vdots A_M B_M C_M
出力
答えの値を出力せよ。
入力例 1
10 2 2 5 1 4 10 3
出力例 1
6
次のように移動するのが最適です。
- 1 階から 2 階まで階段を使って 1 分で移動する。
- 2 階から 5 階まで 1 台目のエレベーターを使って 1 分で移動する。
- 5 階から 4 階まで階段を使って 1 分で移動する。
- 4 階から 10 階まで 2 台目のエレベーターを使って 3 分で移動する。
入力例 2
1000000000000000000 1 1 1000000000000000000 1000000000000000000
出力例 2
999999999999999999
Score : 6 points
Problem Statement
There is an N-story building, with stairs and M direct elevators. (Here, the lowest floor is called the 1-st floor.)
Using stairs, it is possible to travel between the i-th and (i+1)-th floors in either direction in 1 minute, for every i \, (1 \leq i \leq N - 1).
Additionally, using the i-th elevator, it is possible to travel between the A_i-th and B_i-th floors in either direction in C_i minutes, for each i \, (1 \leq i \leq M).
Find the minimum number of minutes needed to get from the 1-st floor to the N-th floor.
Constraints
- 2 \leq N \leq 10^{18}
- 1 \leq M \leq 10^5
- 1 \leq A_i \lt B_i \leq N
- 1 \leq C_i \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 C_1 \vdots A_M B_M C_M
Output
Print the value representing the answer.
Sample Input 1
10 2 2 5 1 4 10 3
Sample Output 1
6
The optimal way to get there is as follows.
- Use stairs to get from the 1-st floor to the 2-nd floor in 1 minute.
- Use the 1-st elevator to get from the 2-nd floor to the 5-th floor in 1 minute.
- Use stairs to get from the 5-th floor to the 4-th floor in 1 minute.
- Use the 2-nd elevator to get from the 4-th floor to the 10-th floor in 3 minutes.
Sample Input 2
1000000000000000000 1 1 1000000000000000000 1000000000000000000
Sample Output 2
999999999999999999