No.1473 The Chubby Ghost
タグ : / 解いたユーザー数 226
作問者 :
null
/ テスター :
👑
hitonanode
nok0
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
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もしくは右上の雲マークをクリックしてアカウントを作成してください。