B. AlgoRace

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

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

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

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

PMP програмчлалын олимпиадад орохын оронд машины урдаанд оролцохоор шийдэв.

AlgorRace нь $n$ хотод явагддаг олон баг оролцсон тусгай лиг юм. Хотууд 1-ээс $n$ хүртэл дугаарлагдсан. Ялгаатай 2 хот тус бүр нэг ширхэг 2 чиглэлт замаар холбогдсон байдаг ба лигт оролцож буй баг бүр нэг жолооч, хэд хэдэн машинуудтай байна.

Уралдаан $r$ үетэй бөгөөд $i$-р үед жолооч нар $s_i$-р хотоос $t_i$-р хот хүртэл уралдана. Жолооч нар машинаа хамгийн ихдээ $k_i$ удаа сольж болох бөгөөд машинаа дурын нэг хотод 0 хугацаанд солиж болдог. Нэг үед нэг машиныг олон дахин ашиглаж болох боловч нийт машинаа сольсон тоо нь $k_i$-аас хэтрэх ёсгүй. Жолооч нар уралдах үедээ замаараа өөрсдөө хүссэнээрээ сонгох боломжтой.

PMP $m$ ширхэг тусгай машинуудтай тэмцээнд оролцох ба PMP жолоодох ур чадвараас гадна тухайн үед ямар зам дээр ямар машинаар уралдаж байгаагаас хамааран зам тус бүрийн чиглэл бүрийг өөр өөр хугацаанд туулдаг.

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

Оролт

Эхний мөрөнд гурван бүхэл тоо $n, m$ ба $r(2<=n<=60, 1<=т<=60ь 1<=r<=10^5)$ буюу хотуудын тоо, машинуудын тоо ба тэмцээний үеүүд байрлана6

Дараа нь $m$ ширхэг $n*n$ матрицууд орж ирэх ба $i$-р матрицын $j$-р мөрний $k$ дахь тоо нь $i$-р машин $j$-р хотоос $k$-р хот ороход зарцуулах хугацааг илэрхийлж байгаа болно. Эдгээр матрицууд заавал тэгш хэмтэй байх албагүй боловч диагоналууд нь ямагт дан 0-үүдээс бүрдэх болно.

Дараагийн $r$ ширхэг мөрөнд үеүүдийн мэдээллүүд байрлах ба эдгээр мөрнүүдийн $i$-р нь хоосон зайгаар тусгаарлагдсан гурван бүхэл тоо $s_i, t_i, k_i(1<=s_i, t_i<=n, s_i!=t_i, 0<=k<=1000)$ -уудаас бүрдэх ба энэ нь эхлэх хотын дугаар, дуусах хотын дугаар болон тухайн үед машины солих боломжийн тоонууд юм.

Гаралт

Үе болгоныг давах хамгийн бага хурдуудыг нэг нэг мөрөнд хэвлэ

Орчуулсан: devman

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

Оролт
4 2 3
0 1 5 6
2 0 3 6
1 3 0 1
6 6 7 0
0 3 5 6
2 0 1 6
1 3 0 2
6 6 7 0
1 4 2
1 4 1
1 4 3
Гаралт
3
4
3
Оролт
4 2 3
0 7 3 3
8 0 10 5
1 1 0 4
8 9 2 0
0 3 3 9
7 0 4 9
3 8 0 4
4 8 9 0
2 3 3
2 1 3
1 2 2
Гаралт
4
5
3

Тэмдэглэл

Эхний жишээнд бүх үеүдэд PMP #1 хотоос #2-р хотод очно, дараагаар нь #3, тэгээд хамгийн сүүлд #4-д очно. Гэвч түүний хэрэглэх машинуудын төрлүүдийн дарааллууд нь эхний үед (1, 2, 1) ба дараагийн үед (1, 2, 2) байна. 3-р үед тэр машинаа гурван удаа сольж чадна хэдий ч зөвхөн хоёр машин хэрэглэгдэх эхний үетэй адилхан стратегийг хэрэглэнэ.

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