問題一覧 > 通常問題

No.1393 Median on Graph

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 18
作問者 : chineristACchineristAC / テスター : tpynerivertpyneriver
4 ProblemId : 5492 / 出題時の順位表
問題文最終更新日: 2021-02-13 14:13:39

お詫び

不正な入力を含むテストケースが確認されました。該当テストケースを削除後、リジャッジします。大変申し訳ございません。

$22:26$ 該当テストケースを削除、リジャッジを行いました。

問題文

$N$ 個の整数からなる数列 $A$ の中央値をつぎのように定義します。

  • $A$ を昇順にソートして得られる数列を $A'$ とする。このとき $A'$ の $(N+1)/2$ 番目の要素を $A$ の中央値とする( $/$ は小数点以下を切り捨てる除算を表す)。

$N$ 頂点 $M$ 辺の重み付き単純有向グラフがあります。$i\ (1\le i \le M)$ 番目の辺は頂点 $u_i$ から頂点 $v_i$ へ向かっており、重みは $w_i$ です。

頂点 $s$ から頂点 $t$ へのパス $p$ に対し、 $median(p)$ を「 $p$ が含む辺の重みの値を昇順に並べて得られる数列 $A$ の中央値」とします。

各 $i=2,\ 3,\ \dots\ N$ について、頂点 $1$ から頂点 $i$ へのパス $p$ に対する $median(p)$ の最小値を出力してください。パスが存在しない場合は $-1$ を出力してください。

入力

$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)$
  • 与えられる入力はすべて整数
  • 与えられるグラフは自己ループや多重辺をもたない

出力

$N-1$ 行出力してください。

$i\ (1\le i \le N-1)$ 行目には頂点 $1$ から頂点 $i+1$ へのパス $p$ に対する $median(p)$ の最小値を出力して下さい。パスが存在しない場合は $-1$ を出力してください。

最後に改行してください。

サンプル

サンプル1
入力
4 5
1 2 3
2 3 19
3 4 11
1 4 19
2 4 15
出力
3
3
3

頂点 $1$ から 頂点 $4$ へのパスは $1→2→3→4, 1→2→4, 1→4$ の $3$ 通りです。

たとえば $1$ 番目のパスの $median(p)$ は $(3,\ 11,\ 19)$ の中央値である $11$ です。

ほかのパスについても同様に $median(p)$ を求めると $3, 19$ になるので、 $3$ 行目にはこれらの最小値である $3$ を出力します。

サンプル2
入力
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
出力
10
5
5
5
5
5
-1

頂点 $1$ から頂点 $7$ へのパス $1→2→3→4→5→3→4→5→3→6→7$ の $median(p)$ は $5$ になり、 $median(p)$ がこれより小さくなるパスは存在しないので $6$ 行目には $5$ を出力します。

頂点 $1$ から頂点 $8$ へのパスは存在しないので $7$ 行目には $-1$ を出力します。

サンプル3
入力
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
出力
12
12
12
11
11
11
15
11
15

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