問題一覧 > 通常問題

No.1393 Median of Walk

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 21
作問者 : chineristAC / テスター : tpyneriver
お気に入りにしたユーザー ProblemId : 5492 / 自分の提出
問題文最終更新日: 2023-04-04 13:15:26
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 282 (順位表) の他の問題:

Problem Statement

The median of a sequence $A$ consisting of $N$ integers is defined as follows.

  • Let $A'$ be the sequence obtained by sorting $A$ in ascending order. Then the $(N+1)/2$-th element of $A'$ is the median of $A$ (here, $/$ denotes division with the fractional part truncated).

There is a weighted directed graph with $N$ vertices and $M$ edges. The $i\ (1\le i \le M)$-th edge goes from vertex $u_i$ to vertex $v_i$ and has weight $w_i$.

For a walk $p=(v_0=s,e_1,v_1,e_2,\dots,v_{n-1},e_n,v_n=t)$ from vertex $s$ to vertex $t$, let $\mathrm{median}(p)$ be the median of the sequence $A=(w_{e_1},w_{e_2},\dots,w_{e_n})$.

For each $i=2,\ 3,\ \dots\ N$, output the minimum value of $\mathrm{median}(p)$ over walks $p$ from vertex $1$ to vertex $i$. If no walk exists, output $-1$.

What is a walk? (click to expand) When an integer sequence $p=(v_0,e_1,v_1,\dots,v_{n-1},e_n,v_n)$ satisfies the following conditions, $p$ is said to be a walk from vertex $s$ to vertex $t$.
  • $v_0=s,v_n=t$
  • Edge $e_i$ is an edge going from vertex $v_{i-1}$ to vertex $v_i$
Note that, unlike a (simple) path, a walk may pass through the same vertex or the same edge more than once.

Input

$N\ M$
$u_1\ v_1\ w_i$
$\vdots$
$u_M\ v_M\ w_M$

  • $2 \le N \le 1000$
  • $1 \le M \le \min(\frac{N(N-1)}{2},\ 2500)$
  • $1 \le u_i,\ v_i \le N\ (1\le i \le M)$
  • $1\le w_i \le 10^9\ (1\le i \le M)$
  • All values in the input are integers
  • The given graph has no self-loops or multiple edges

Output

Output $N-1$ lines.

On the $i\ (1\le i \le N-1)$-th line, output the minimum value of $\mathrm{median}(p)$ over walks $p$ from vertex $1$ to vertex $i+1$. If no walk exists, output $-1$.

Print a newline at the end.

Sample

Sample 1
Input
4 5
1 2 3
2 3 19
3 4 11
1 4 19
2 4 15
Output
3
3
3

(For clarity, walks are represented as vertex sequences in the sample explanations below.)

The walks from vertex $1$ to vertex $4$ are the following $3$: $1→2→3→4, 1→2→4, 1→4$.

For example, $\mathrm{median}(p)$ of the $1$-st walk is $11$, which is the median of $(w_1,w_2,w_3)=(3,\ 19,\ 11)$.

Computing $\mathrm{median}(p)$ for the other walks in the same way gives $3, 19$, so on the $3$-rd line we output $3$, the minimum of these values.

Sample 2
Input
8 8
1 2 10
2 3 11
3 4 5
4 5 8
5 3 2
3 6 12
6 7 19
8 5 4
Output
10
5
5
5
5
5
-1

The walk $1→2→3→4→5→3→4→5→3→6→7$ from vertex $1$ to vertex $7$ has $\mathrm{median}(p)$ equal to $5$, and no walk has a smaller $\mathrm{median}(p)$, so we output $5$ on the $6$-th line.

There is no walk from vertex $1$ to vertex $8$, so we output $-1$ on the $7$-th line.

Sample 3
Input
10 20
1 2 12
2 3 81
2 4 50
3 5 98
5 6 75
6 7 15
3 8 40
3 9 75
7 10 86
1 5 11
2 9 99
8 9 12
6 9 96
1 3 93
5 9 37
5 7 17
7 8 96
1 8 49
2 7 79
4 7 82
Output
12
12
12
11
11
11
15
11
15

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。