E. Классик бодлого

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 768 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$n$ оройтой, $m$ ирмэгтэй, жинтэй, чиглэлгүй граф ѳгѳгдсѳн. $s$ оройгоос $t$ орой хүртэлх хамгийн бага замыг ол, эсвэл тийм зам олдохгүй гэдгийг илтгэ.

Оролт

Эхний мѳр $n$, $m$ ($1 ≤ n ≤ 10^{5}$; $0 ≤ m ≤ 10^{5}$) тоог агуулна.

Дараагийн $m$ мѳр графийн ирмэгүүдийг илэрхийлнэ. $i$-р мѳрѳнд зайгаар тусгаарлагдсан $u_{i}$, $v_{i}$, $x_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$; $0 ≤ x_{i} ≤ 10^{5}$) бүхэл тоонууд байрлана. Энэ нь $u_{i}$, $v_{i}$ оройнууд $2^{x_{i}}$ ($2$-ын $x_{i}$ зэрэг) урттай ирмэгээр холбогдсон гэсэн утгатай.

Сүүлийн мѳр замын эцсийн оройнуудын дугаар болох $s$, $t$ бүхэл тоог агуулна.

Оройнууд $1$-ээс $n$ хүртэл дугаарлагдна. Уг графд давхар ирмэг болон гогцоо байхгүй.

Гаралт

Эхний мѳрѳнд хэрвээ тийм зам байгаа бол уртыг нь $1000000007 (10^{9} + 7)$ тоонд хуваасан үлдэгдлийг, байхгүй бол $-1$ гэж хэвлэ.

Тийм зам олддог бол хоёрдугаар мѳрѳнд $s$ оройгоос $t$ орой хүртэл туулах замын оройнуудын тоо болох $k$ тоог хэвлэ; гуравдугаар мѳрѳнд уг замын очсон дарааллаар нь илэрхийлэх $k$ ширхэг тоог зайгаар тусгаарлан хэвлэ. Эхний орой нь $s$, сүүлийн орой нь $t$ байх ёстой. Хамгийн богино зам олон байвал дуртайгаа хэвлэ.

Орчуулсан: Sugardorj

Жишээ тэстүүд

Оролт
4 4
1 4 2
1 2 0
2 3 0
3 4 0
1 4
Гаралт
3
4
1 2 3 4 
Оролт
4 3
1 2 4
2 3 5
3 4 6
1 4
Гаралт
112
4
1 2 3 4 
Оролт
4 2
1 2 0
3 4 1
1 4
Гаралт
-1

Тэмдэглэл

$s$ оройгоос $t$ орой хүрэх зам гэж $v_{0} = s$, $v_{k} = t$ ба $0$-ээс $k - 1$ хүртэлх $i$ тоонуудын хувьд $v_{i}$, $v_{i + 1}$ оройнууд ирмэгээр холбогдсон байх $v_{0}$, ..., $v_{k}$ дарааллыг хэлнэ.

Замын урт нь $v_{i}$, $v_{i + 1}$ оройнуудыг холбосон ирмэгийн жингүүдийн нийлбэр байна.

$s$ оройгоос $t$ орой хүрэх хамгийн богино зам гэж $s$ оройгоос $t$ орой хүрэх замуудаас хамгийн бага урттайг нь хэлнэ.

Сэтгэгдлүүдийг ачааллаж байна...