Catun

catun

==Include(page="template/taskheader" task_id="catun")==

== include(page="template/taskheader" task_id="catun") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| catun.in | catun.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="catun") ==

==Include(page="template/raw")==
 
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.
 
h2. Cerinta
 
Sa se determine pentru fiecare catun carei fortarete apartine.
 
h2. 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 si are lungimea z, exprimata in unitatea de masura pentru lungimi a Evului Mediu.
 
h2. 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.
 
h2. Restrictii si precizari
 
o 1 <= K <= N <= 36 000
o 1 <= M <= 72 000
o Intre oricare doua asezari exista maxim un drum
 
h2. Exemplu
 
 
 
catun.in catun.out
8 9 2 5 0 5 0 0 5 0 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
 
 
==Include(page="template/taskfooter" task_id="catun")==