Codeforces Round #803 (Div. 2)
04:36:29 |
Codeforces Round #804 (Div. 2)
6 өдрийн дараа |
D. Байнгын үйлчлүүлэгчдэд зориулсан нислэгүүд
хугацааны хязгаарлалт 4 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Энэ улсад $1$-c $n$ хүртэл эерэг бүхэл тоон утгаар дугаарлагдсан яг $n$ хот бий. Хот бүрт энэ хотод байрласан нисэх буудал байдаг.
Мөн энд $m$ нислэг хийдэг ганцхан нисэх компани бий. Харамсалтай нь эдгээр нислэгийг ашиглахын тулд та энэ компаны байнгын үйлчлүүлэгч байх ёстой ба өөрөөр хэлбэл та $a_{i}$ хотоос $b_{i}$ хот хүрэх $i$ нислэгийн өмнө хамгийн багадаа $d_{i}$ нислэг хийчихсэн байх ёстой ба ингэж байж энэ нислэгт багтах боломжтой.
$i$ нислэг нь яг $a_{i}$ хотоос $b_{i}$ хотруу ниснэ. Энэ нь $b_{i}$ хотоос $a_{i}$ хотруу нисэхэд ашиглагдаж чадахгүй. Нэг сонирхолтой зүйл бол нэг хотоос гарч уг хотдоо ирдэг тэнгэрийн үзэсгэлэнт хэсгээр явах зугаа цэнгэлийн нислэгүүд байж болно.
Та $1$-р хотоос $n$-р хотод хүрэх хэрэгтэй. Харамсалтай нь та өмнө нь онгоцоор аялаж байгаагүй. Та $n$ хотод хүрэхийн тулд хамгийн багадаа хэдэн нислэг үйлдэх вэ?
Нэг нислэг хэд хэдэн удаа ашиглагдаж болно.
Оролт
Эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($2 ≤ n ≤ 150$, $1 ≤ m ≤ 150$) байх ба тус улсын хотуудын тоо болон компаний үйлчилдэг нислэгүүдийн тоо.
Дараагийн $m$ мөрөнд $a_{i}$, $b_{i}$, $d_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $0 ≤ d_{i} ≤ 10^{9}$) тоонуудыг агуулах ба $a_{i}$ хотоос $b_{i}$ хот хүрэх дугаартай нислэгийг илэрхийлэх ба зөвхөн хамгийн багадаа $d_{i}$ нислэг хийсэн байх үйлчлүүлэгчдэд нээлттэй.
Гаралт
Хэрвээ агаарын замыг ашиглан $1$ дугаартай хотоос $n$ дугаартай хот хүрэх боломжгүй бол "$Impossible$" (хашилтгүйгээр) гэж хэвлэ.
Гэхдээ ядаж нэг зам байвал та эцсийн цэгт очиход хийх шаардлагатай нислэгүүдийн хамгийн бага тоог илэрхийлэх бүхэл тоон утгыг хэвлэ.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
3 2 1 2 0 2 3 1
Гаралт
2
Оролт
2 1 1 2 100500
Гаралт
Impossible
Оролт
3 3 2 1 0 2 3 6 1 2 0
Гаралт
8