Fişierul intrare/ieşire:catun.in, catun.outSursăLista lui Francu
AutorCatalin FrancuAdăugată de
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Catun

Intr-un regat feudal exista mai multe asezari omenesti, numerotate de la 1 la N, intre care sunt construite drumuri de diverse lungimi. Dintre aceste asezari, o parte sunt fortarete, iar restul sunt simple catune. Fiecare fortareata trebuie sa aprovizioneze trupele stationate in ea, deci are nevoie de feude. In calitate de mare sfetnic al monarhului, vi se cere sa indicati feudele aservite fiecarei fortarete, respectiv toate acele catune care se afla mai aproape de fortareata in discutie decat de oricare alta. Daca un catun este la distanta egala de doua fortarete, se va considera ca apartine fortaretei cu numarul de identificare minim.

Cerinta

Sa se determine pentru fiecare catun carei fortarete apartine.

Date de Intrare

In fisierul de intrare catun.in se vor afla numarele N, M, K, indicand, in aceasta ordine, numarul de asezari, numarul de drumuri si numarul de fortarete. Cea de a doua linie a fisierului va contine K numere naturale distincte indicand numerele de ordine ale fortaretelor. Pe urmatoarele M linii, pana la sfarsitul fisierului, se vor gasi triplete de forma (x y z), semnificand faptul ca exista un drum bidirectional intre asezarile x si y de lungime z, exprimata in unitatea de masura pentru lungimi a Evului Mediu.

Date de Iesire

Fisierul de iesire catun.out va contine o singura linie pe care se afla N numere naturale, al i-lea numar fiind 0, daca asezarea a i-a este o fortareata sau este un catun de la care nu se poate ajunge la nici o fortareata din cele K, sau numarul fortaretei de care se leaga asezarea a i-a, in caz contrar.

Restrictii si precizari

  • 1 ≤ K ≤ N ≤ 36 000
  • 1 ≤ M ≤ 72 000
  • Intre oricare doua asezari exista maxim un drum

Exemplu

catun.incatun.out
8 9 2
2 5
1 3 6
1 5 3
1 6 1
2 3 9
5 6 5
6 8 7
3 6 2
4 7 1000
2 8 5
5 0 5 0 0 5 0 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content