No.3653 Space-Time Courier
タグ : / 解いたユーザー数 31
作問者 :
とある理系大学生の日常
Problem Statement
The galaxy has $N$ stations (1, 2, ..., $N$), connected by $M$ one-way space-time warp gates.
The $i$-th warp gate allows travel from station $u_i$ to station $v_i$, and the travel takes time $t_i$.
Due to space-time distortion, some gates may rewind time ($t_i < 0$), but it is guaranteed that there is no cycle that would allow going back in time indefinitely (negative cycle).
Each station $i$ has a "base cost" $P_i$.
When a spaceship departs from station $A$ and delivers a package to station $B$ ($A \neq B$) via some gates, the total cost of the delivery is defined as follows.
$$\text{Cost}(A, B) = (\text{station } A \text{ to } B \text{ minimum travel time}) + P_A + P_B$$
Find the minimum value of $\text{Cost}(A, B)$ over all pairs $(A, B)$ of distinct stations such that the destination is reachable.
Also, find how many pairs $(A, B)$ achieve that minimum value.
It is guaranteed that there exists at least $1$ reachable pair of stations $(A, B)$.
Constraints
- $2 \le N \le 2500$
- $1 \le M \le 5000$
- $1 \le u_i, v_i \le N$
- $u_i \neq v_i$
- $(u_i, v_i) \neq (u_j, v_j)$ if $i \neq j$
- $-10^6 \le t_i \le 10^6$
- $-10^9 \le P_i \le 10^9$
- The graph has no negative cycles.
- All input values are integers.
Input
The input is given from standard input in the following format.
$N$ $M$ $P_1$ $P_2$ $\dots$ $P_N$ $u_1$ $v_1$ $t_1$ $u_2$ $v_2$ $t_2$ $\vdots$ $u_M$ $v_M$ $t_M$
Output
Print the minimum cost and the number of pairs achieving that minimum cost on 1 line, separated by a space.
If no reachable pair exists, print -1.
End the output with a newline.
Sample
Sample 1
Input
4 4 10 20 15 25 1 2 5 2 3 5 1 3 12 3 4 5
Output
35 2
The cost of each pair is as follows.
- $(1, 2)$: travel time 5, $\text{Cost}(1, 2) = 5 + 10 + 20 = 35$
- $(2, 3)$: travel time 5, $\text{Cost}(2, 3) = 5 + 20 + 15 = 40$
- $(3, 4)$: travel time 5, $\text{Cost}(3, 4) = 5 + 15 + 25 = 45$
- $(1, 3)$: travel time 10 (going via $1 \to 2 \to 3$ is shorter than the direct 12), $\text{Cost}(1, 3) = 10 + 10 + 15 = 35$
- $(2, 4)$: travel time 10 (via $2 \to 3 \to 4$), $\text{Cost}(2, 4) = 10 + 20 + 25 = 55$
- $(1, 4)$: travel time 15 (via $1 \to 2 \to 3 \to 4$), $\text{Cost}(1, 4) = 15 + 10 + 25 = 50$
The minimum cost is 35, and the 2 pairs achieving it are $(1, 2)$ and $(1, 3)$.
Sample 2
Input
4 4 0 0 0 0 1 2 -5 2 3 -5 3 1 15 4 1 10
Output
-10 1
Computing the cost of each pair, the minimum travel time of $(1, 3)$ is $-10$, and $\text{Cost}(1, 3) = -10 + 0 + 0 = -10$ is the minimum value.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。