N хот болон M чиглэлтэй зам бүхий граф өгөгдөнө. Энэхүү граф нь cycle-гүй (DAG) байна.

Зам бүр:

• эхлэл хот u
• төгсгөл хот v
• жин (оноо) w

Та 1-р хотоос эхэлж N-р хот хүртэл очих ёстой.

? Нэмэлт боломж (Boost)

Та аяллын явцад хамгийн ихдээ K удаа "boost" ашиглаж болно.

Boost ашиглах үед:

-тухайн замын оноо 2 дахин нэмэгдэнэ

⚠️ Нэмэлт нөхцөл

• Та зөвхөн замын чиглэлийн дагуу явна
• Нэг зам дээр boost хэрэглэвэл зөвхөн тэр замд нөлөөлнө
• Нэг замд boost ашиглах эсэхээ өөрөө шийднэ

? Зорилго

? 1-ээс N хүртэлх замаар явж авах хамгийн их оноо-г ол

Хэрэв N хот хүрэх боломжгүй бол -1 хэвлэнэ

Оролт:

N M K
u1 v1 w1
u2 v2 w2
...
uM vM wM

• N — хотын тоо
• M — замын тоо
• K — boost ашиглах дээд тоо
• (ui, vi) — чиглэлтэй зам
• wi — замын оноо

Гаралт:

хамгийн их боломжит оноо эсвэл -1

Хязгаарлалтууд:

• 1 ≤ N ≤ 2 × 10⁵
• 1 ≤ M ≤ 2 × 10⁵
• 0 ≤ K ≤ 10
• -10⁹ ≤ w ≤ 10⁹

Дэд бодлого

Жишээ:

Оролт-1

4 4 1
1 2 5
2 4 5
1 3 3
3 4 10

Гаралт-1

23

Тайлбар-1

Боломжит замууд:

Зам 1:

1 → 2 → 4 Оноо:

5 + 5 = 10

Boost хэрэглэвэл:

10 + 5 = 15 (нэг edge-ийг 2x болгоно) Зам 2:

1 → 3 → 4 Оноо:

3 + 10 = 13

Boost-ийг 10 дээр хэрэглэвэл:

3 + (10×2) = 23

? Хамгийн их нь: 23

Оролт-2

3 1 2
1 2 5

Гаралт-2

-1

Тайлбар-2

3-р хот хүрэх зам байхгүй ? Хариу: -1