問題一覧 > 通常問題

No.1473 おでぶなおばけさん

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 154
作問者 : 👑 nullnull / テスター : 👑 hitonanodehitonanode nok0nok0
30 ProblemId : 6227 / 出題時の順位表
問題文最終更新日: 2021-04-05 23:41:22

問題文

ある日、shojin 王国に体重 $10^{10^9}[kg]$ のちょっぴりおでぶなおばけさんが引っ越してきました。

shojin 王国は $n$ 個の都市からなっており、都市には順番に都市 $1$ 、都市 $2$ 、 $\dots$ 、都市 $n$ と名前がついています。$ m$ 本の道が都市同士を繋いであり、同様に道 $1$ 、道 $2$ 、 $\dots$ 、道 $m$ と名前がついています。 $i(1 \le i \le m)$ 番目の道は都市 $s_i$ と都市 $t_i(s_i \neq t_i)$ をつないでおり、双方向に通行可能です。すべての $1 \le a, b \le n$ について、いくつかの道を使い都市 $a$ から都市 $b$ にたどり着けることが保証されます。 また、$i$ 番目の道は $d_i[kg]$ までしか耐えられません。

おばけさんは最初都市 $1$ にいて、いくつかの道を通って都市 $n$ に行きたいです。

しかし、おばけさんの体重を $w[kg]$ としたとき、$w > d_i$ を満たす $i$ について、道 $i$ は崩壊の危険性があるため使えません。

ダイエットが上手ではないおばけさんのために、都市 $1$ から都市 $n$ に到達可能な体重 $w$ の 最大値 及び、$w$ が最大値の時都市 $1$ から都市 $n$ に到達するために通る必要のある道の数の 最小値 を求めてください。

制約

  • $2 \le n \le 10^5$
  • $n - 1 \le m \le 10^5$
  • $1 \le s_i, t_i \le n$
  • $s_i \neq t_i$
  • $1 \le d_i \le 10^9$
  • すべての $1 \le a, b \le n$ について、いくつかの道を使い都市 $a$ から都市 $b$ にたどり着けることが保証される。
  • 入力は全て整数
  • 入力

    $n\ m$
    $s_1\ t_1\ d_1$
    $s_2\ t_2\ d_2$
    $\vdots$
    $s_m\ t_m\ d_m$
    

    出力

    都市 $1$ から都市 $n$ に到達可能な体重 $w$ の最大値及び、$w$ が最大値の時都市 $1$ から都市 $n$ に到達するために通る必要のある道の数の最小値を、空白区切り で出力してください。 最後に改行してください。

    サンプル

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

    $w=3$ の時、都市 $1$ と都市 $2$ を繋ぐ道と、都市 $2$ と都市 $3$ を繋ぐ道を通ることができ、これが最短路です。

    サンプル2
    入力
    3 4
    1 3 999999999
    1 2 999999999
    2 3 999999999
    1 3 999999998
    
    出力
    999999999 1
    

    $w=999999999$ の時、都市 $1$ と都市 $3$ を繋ぐ道を通ることができます。また、同じ都市同士を繋ぐ道があるかもしれません。

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