Codeforces Round #803 (Div. 2)
05:52:14 |
Codeforces Round #804 (Div. 2)
6 өдрийн дараа |
C. Dijkstra?
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 64 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Таньд жинтэй чиглэлгүй граф өгөгджээ. Таны даалгавар өгөгдсөн графын хувьд $1$-р оройгоос $n$-р орой хүрэх хамгийн богино замыг олох юм.
Оролт
Эхний мөрөнд $n$ ба $m$ ($2 ≤ n ≤ 10^5; 0 ≤ m ≤ 10^5$). Энд $n$ нь оройн тоо ба $m$ нь ирмэгийн тоо.
Дараагийн $m$ мөрөнд $a_i$, $b_i$ ба $w_i$ ($1 ≤ a_i, b_i ≤ n; 1 ≤ w_i ≤ 10^6$) $a_i$ ба $b_i$ ирмэгүүд хоорондоо $w_i$ жинтэй ирмэгээр холбогдсоныг илэрхийлсэн тоонууд өгөгдөнө.
Гаралт
$1$-р оройгоос $n$-р оройд хүрэх зам олддог бол $1$-р оройгоос $n$-р оройд хүрэх замд таарах оройн дугааруудыг хэвлэнэ үү?
Энэ бодлого олон хариутай тул аль нэг хариуг хэвлэхэд болно. Хэрэв боломжгүй бол $-1$ гэж хэвлэнэ үү?
Орчуулсан: Адъяа
Жишээ тэстүүд
Оролт
5 6 1 2 2 2 5 5 2 3 4 1 4 1 4 3 3 3 5 1
Гаралт
1 4 3 5
Оролт
5 6 1 2 2 2 5 5 2 3 4 1 4 1 4 3 3 3 5 1
Гаралт
1 4 3 5