== include(page="template/taskheader" task_id="lanterna") ==
==Include(page="template/taskheader" task_id="lanterna")==
Poveste ...
Un agent secret are o harta pe care sunt marcate $N$ obiective militare. El se afla, initial, langa obiectivul numerotat cu 1 (baza militara proprie) si trebuie sa ajunga la obiectivul numerotat cu $N$ (baza militara inamica). Pentru aceasta, el va folosi drumurile existente, fiecare drum legand 2 obiective distincte. Fiind o misiune secreta, deplasarea agentului va avea loc noaptea; de aceea, el are nevoie de o lanterna. Pentru aceasta, el are de ales intre $K$ tipuri de lanterne - o lanterna de tipul $W (1 ≤ W ≤ K)$ are baterii care permit consumul a $W$ watti; dupa consumul acestor watti, lanterna nu mai lumineaza. Din fericire, unele dintre obiective sunt baze militare prietene, astfel ca, o data ajuns acolo, el isi poate reincarca complet bateriile. Agentul trebuie sa aiba grija ca, inainte de merge pe un drum intre doua obiective, cantitatea de watti pe care o mai poate consuma sa fie mai mare sau egala cu cantitatea de watti pe care o va consuma pe drumul respectiv.
Cunoscand drumurile dintre obiective si, pentru fiecare drum, durata necesara parcurgerii drumului si numarul de watti consumati de lanterna, determinati tipul de lanterna cu numarul cel mai mic, astfel incat durata deplasarii sa fie minima (sa presupunem ca acest tip este $W$; aceasta inseamna ca daca ar alege o lanterna de un tip mai mic decat $W$, durata deplasarii ar fi strict mai mare, iar daca ar alege o lanterna de un tip mai mare decat $W$, durata deplasarii ar fi mai mare sau egala).
h2. Cerinta
h2. Date de Intrare
...
Pe prima linie a fisierului $lanterna.in$ se afla numerele intregi $N$ si $K$, separate printr-un spatiu. Pe urmatoarea linie se afla $N$ numere intregi din multimea ${0,1}$. Daca al $i$-lea numar este $1$, aceasta inseamna ca obiectivul cu numarul $i$ este o baza militara prietena (adica agentul isi poate reincarca bateriile lanternei daca ajunge la acest obiectiv); daca numarul este 0, agentul nu isi va putea reincarca bateriile. Pe cea de-a treia linie a fisierului se afla numarul $M$ de drumuri dintre obiective. Fiecare din urmatoarele $M$ linii contine cate 4 numere intregi separate prin spatii: $a b T W$, avand semnificatia ca exista un drum bidirectional intre obiectivele $a$ si $b$ $(a<>b)$, care poate fi parcurs intr-un timp $T$ si cu un consum de $W$ watti.
h2. Restrictii
h2. Date de Iesire
...
In fisierul $lanterna.out$ veti afisa doua numere intregi, separate printr-un spatiu : $Tmin$ si $W$. Tmin reprezinta durata minima posibila a deplasarii de la obiectivul 1 la obiectivul $N$, iar $W$ reprezinta tipul de lanterna cu numarul cel mai mic pentru care se obtine acest timp.
h2. Date de intrare
h2. Restrictii si precizari
...
h2. Date de iesire
...
* $2 ≤ N ≤ 50$
* $1 ≤ K ≤ 1000$
* $1 ≤ M ≤ N*(N-1)/2$
* Intre doua orase diferite poate exista maxim un drum direct.
* Pentru fiecare drum, durata parcurgerii este un numar intreg intre $1$ si $100$, iar numarul de watti consumati este un numar intreg intre $0$ si $1000$
* Se garanteaza ca exista cel putin un tip de lanterna pentru care deplasarea sa fie posibila.
h2. Exemplu
| lanterna.in | lanterna.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. lanterna.in |_. lanterna.out |
| 7 10
0 0 1 0 0 0 0
7
1 2 10 3
1 4 5 5
2 3 10 3
4 3 15 1
3 6 4 3
6 5 2 2
5 7 1 0 | 27 6 |
== include(page="template/taskfooter" task_id="lanterna") ==
==Include(page="template/taskfooter" task_id="lanterna")==
