問題一覧 > 通常問題

No.3653 Space-Time Courier

レベル : / AI推定難易度 : 1625 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 31
作問者 : Rino-program / テスター : gomaazarasi とある理系大学生の日常
お気に入りにしたユーザー ProblemId : 13697 / 自分の提出
問題文最終更新日: 2026-08-28 21:02:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 511 (Div.2) (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。