問題一覧 > 通常問題

No.1607 Kth Maximum Card

レベル : / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 89
作問者 : 👑 SPD_9X2SPD_9X2 / テスター : 👑 tute7627tute7627 penguinmanpenguinman
4 ProblemId : 6252 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-14 17:29:44

問題文

$N$ 頂点 $M$ 辺の単純無向グラフが与えられます。グラフ全体は連結であることが保証されます。

辺 $i$ ($1 \le i \le M$) は、頂点 $u_i$ と $v_i$ を結んでおり、パラメータ $c_i$ を持ちます。

せねこさんは袋を持っており、その中には最初 $0$ が書かれたカード $K$ 枚が入っています。

せねこさんは、頂点 $1$ からスタートしてグラフ上を旅します。

せねこさんは辺 $i$ を通った時、 $c_i$ が書かれたカードを袋の中に $1$ 枚入れます。(同一の辺を複数回通った場合、その度にカードを $1$ 枚入れます)

旅を始めてからしばらくして、せねこさんは頂点 $N$ にいました。 この時、袋の中に入っているカードを降順に並べた場合に $K$ 番目にくるカードに書かれている数として考えられる最小のものを求めてください。

ただし、せねこさんは辺で接続された $2$ 頂点間のみを移動し、 $2$ 回以上同じ辺を利用することもあることに注意してください。

入力

$N\ M\ K$
$u_1\ v_1\ c_1$
$u_2\ v_2\ c_2$
$\vdots$
$u_M\ v_M\ c_M$

  • 入力は全て整数
  • 与えられるグラフは連結な単純無向グラフ
  • $2 \le N \le 2 \times 10^5$
  • $N-1 \le M \le \mathrm{min}\left(2 \times 10^5, \frac{N (N - 1)} {2}\right)$
  • $1 \le K \le 2 \times 10^5$
  • $1 \le u_i < v_i \le N$
  • $i \neq j $ であれば $(u_i,v_i) \neq (u_j,v_j)$
  • $1 \le c_i \le 2 \times 10^5$

出力

答えを1行に出力してください。最後に改行してください。

サンプル

サンプル1
入力
2 1 1
1 2 100
出力
100

サンプル2
入力
2 1 2
1 2 100
出力
0

最初から袋に入っていた0のカードが2番目に大きいカードとなります。

サンプル3
入力
4 4 2
1 2 50
2 4 50
1 3 100
3 4 1
出力
1

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