問題一覧 > 通常問題

No.1473 The Chubby Ghost

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 226
作問者 : null / テスター : 👑 hitonanode nok0
お気に入りにしたユーザー ProblemId : 6227 / 自分の提出
問題文最終更新日: 2022-04-25 23:38:43
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 290 (順位表) の他の問題:

Problem Statement

One day, a slightly chubby ghost weighing $10^{10^9}[kg]$ moved to the Kingdom of shojin.

The Kingdom of shojin consists of $n$ cities, named city $1$, city $2$, $\dots$, city $n$ in order. $ m$ roads connect the cities, and they are similarly named road $1$, road $2$, $\dots$, road $m$. The $i(1 \le i \le m)$-th road connects city $s_i$ and city $t_i(s_i \neq t_i)$ and can be traversed in both directions. It is guaranteed that for all $1 \le a, b \le n$, city $b$ can be reached from city $a$ by using some roads. Also, the $i$-th road can only withstand up to $d_i[kg]$.

The ghost is initially in city $1$ and wants to go to city $n$ by traveling along some roads.

However, letting $w[kg]$ be the ghost's weight, for each $i$ satisfying $w > d_i$, road $i$ cannot be used because it is at risk of collapsing.

For the sake of the ghost, who is not good at dieting, find the maximum weight $w$ with which city $n$ can be reached from city $1$, and the minimum number of roads that must be traversed to reach city $n$ from city $1$ when $w$ is that maximum value.

Constraints

  • $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$
  • It is guaranteed that for all $1 \le a, b \le n$, city $b$ can be reached from city $a$ by using some roads.
  • All inputs are integers.
  • Input

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

    Output

    Print the maximum weight $w$ with which city $n$ can be reached from city $1$, and the minimum number of roads that must be traversed to reach city $n$ from city $1$ when $w$ is that maximum value, separated by a space. Print a newline at the end.

    Sample

    Sample 1
    Input
    3 3
    1 3 2
    1 2 3
    2 3 4
    
    Output
    3 2
    

    When $w=3$, the ghost can traverse the road connecting city $1$ and city $2$ and the road connecting city $2$ and city $3$, and this is the shortest path.

    Sample 2
    Input
    3 4
    1 3 999999999
    1 2 999999999
    2 3 999999999
    1 3 999999998
    
    Output
    999999999 1
    

    When $w=999999999$, the ghost can traverse the road connecting city $1$ and city $3$. Note that there may be multiple roads connecting the same pair of cities.

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