Автобус Компаниуд

2s

512MB

2244

0%

Advanced Graph Problems

$n$ хот, $m$ автобус компани байна. Компани бүр тодорхой хотуудад үйлчилгээ үзүүлж, тодорхой үнээр тасалбар зарна. Компанийн тасалбар авбал тухайн компани үйлчилгээ үзүүлдэг хоёр хотын хооронд чөлөөтэй явах боломжтой.

Сиржалэ хотоос хот бүрт очих хамгийн хямд замын өртгийг ол.

https://cses.fi/problemset/task/3158

Оролтын формат

Эхний мөрөнд $n$ ба $m$ гэсэн хоёр бүхэл тоо: хотын болон автобус компанийн тоо. Хотууд $1,2,\dots,n$ гэж дугаарлагдсан ба $1$ дугаартай хот Сиржалэ юм.

Дараагийн мөрөнд $m$ бүхэл тоо $c_1, c_2,\dots, c_m$ : автобус компани бүрийн тасалбарын үнүүд.

Дараа нь компани бүрийн хотуудыг тайлбарласан $m$ хос мөр байна.

Хос бүрийн эхний мөрөнд ганц $k$ бүхэл тоо: компани үйлчилгээ үзүүлдэг хотын тоо.

Хос бүрийн хоёр дахь мөрөнд $k$ хоорондоо ялгаатай бүхэл тоо $a_1, a_2,\dots, a_k$ : компани үйлчилгээ үзүүлдэг хотууд.

Сиржалэ хотоос бусад бүх хот руу явах боломжтой гэж үзэж болно.

Гаралтын формат

$n$ бүхэл тоо хэвлэ: Сиржалэ хотоос $1,2,\dots, n$ хотууд руу очих хамгийн хямд замын өртгүүд.

Хязгаарлалт

$1 \le n, m \le 10^5$
$1 \le c \le 10^9$
$2 \le k \le n$
$1 \le a \le n$
бүх $k$ -ийн нийлбэр $2 \cdot 10^5$ -аас ихгүй

Жишээ

Оролт1

Гаралт1

0 5 4 4 3

0.1 / 64 KiB

Редактор уншиж байна...