| Fişierul intrare/ieşire: | curcani.in, curcani.out | Sursă | Summer Challenge 2021 |
| Autor | Alexandru Luchianov | Adăugată de |  comisia summer 2k21 •summer21 |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Curcani
Aflând de intenţiile lui Rick de a se transforma într-un curcan de Ziua Recunosţintei pentru a nu mai fi marcat drept terorist, preşedintele Curtis se hotărăşte să trimită o armată de curcani pe urmele lui. Reşedinţa preşedintelui se află în oraşul cu numărul 1, iar Rick se află în oraşul N. Oraşele sunt conectate între ele prin M străzi unidirecţionale de diferite lungimi. Curcanii se află iniţial în nodul 1 şi vor să ajungă la Rick, adică în nodul N, mergand pe cel mai scurt drum.
Rick are posibilitatea să mărească lungimile muchiilor pentru a încetini armata de curcani, dar cu un anumit cost. Mai exact, costul pentru a mări muchia i cu j unităţi este A[i][j]. Pentru a căştiga timp, Rick vrea să mărească muchiile grafului astfel încât lungimea celui mai scurt drum de 1 la N să fie cu K unităţi mai mare decât era iniţial. În plus, ştim că A[i][j-1] - A[i][j-2] <= A[i][j] - A[i][j-1].
Ajutaţi-l pe Rick să afle costul minim pentru ca lugimea celui mai scurt drum de la 1 la N să fie cu cel putin K unităţi mai mare decât era iniţial.
Date de intrare
Fişierul de intrare curcani.in conţine pe prima linie numerele N, M şi K reprezentând numărul de noduri, numărul de muchii, respectiv valoarea cu care trebuie marită lungimea drumului minim. Pe linia i + 1 (1 ≤ i ≤ M) , se află x,y,z separate prin câte un spaţiu, reprezentând faptul că există o muchie orientată de la x la y de lungime z. În continuare urmează M linii cu câte K numere reprezentând costurile de mărire ale muchiilor. Al j-lea element de pe linia M + 1 + i reprezintă costul pentru a creste lungimea muchiei i cu j unităţi. ( 1 ≤ i ≤ M, 1 ≤ j ≤ K )
Date de ieşire
În fişierul de ieşire curcani.out se va afla o singură valoare repezentând costul minim cerut.
Restricţii
- 1 ≤ K ≤ 5
- 1 ≤ N ≤ 250
- 1 ≤ M ≤ 1000
- Se garantează că graful aciclic si exista cel putin un drum de la 1 la N.
- 0 ≤ A[i][j] ≤ 10^9
- A[i][j-1] ≤ A[i][j]
- Muchiile au lungimea initiala ≤ 10^9
- Pot exista mai multe muchii între aceeaşi pereche de noduri
Subtaskuri
- Subtaskul 1 (10 de puncte): N ≤ 8; K ≤ 2; M ≤ 12
- Subtaskul 2 (20 de puncte): Graful este format din mai multe lanţuri independente de la 1 la N.
- Subtaskul 3 (20 de puncte): Nodurile de la 1 la N-1 formează un arbore, iar toate frunzele acestuia sunt conectate de nodul N.
- Subtaskul 4 (20 de puncte): K = 1.
- Subtaskul 5 (30 de puncte): restricţiile iniţiale.
Exemplu
| curcani.in | curcani.out |
|---|---|
| 5 7 1 1 2 41 1 5 45 2 3 1 2 4 2 3 5 3 4 5 2 4 5 2 1 1 3 3 4 2 4 | 2 |
| 6 13 2 1 3 103 1 3 104 1 5 113 3 2 7 2 4 14 2 5 4 2 6 20 5 6 18 5 4 12 5 4 11 4 6 7 4 6 7 4 6 6 12 35 12 35 12 34 11 32 11 32 11 33 11 33 12 36 11 32 12 35 12 36 12 36 11 33 | 45 |
Explicaţie
Pentru primul exemplu trebuie incrementate primele 2 muchii cu cate o unitate.
Pentru al doilea exemplu va trebui sa ne credeţi pe cuvânt.
