Fişierul intrare/ieşire:lanterna.in, lanterna.outSursăOJI 2004
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Lanterna

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).

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.

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.

Restrictii si precizari

  • 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.

Exemplu

lanterna.inlanterna.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content