== include(page="template/taskheader" task_id="catun") ==
==Include(page="template/taskheader" task_id="catun")==
Poveste ...
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. Restrictii
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$ de lungime $z$, exprimata in unitatea de masura pentru lungimi a Evului Mediu.
h2. Date de intrare
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. Date de iesire
h2. Restrictii si precizari
...
* $1 ≤ K ≤ N ≤ 36 000$
* $1 ≤ M ≤ 72 000$
* Intre oricare doua asezari exista maxim un drum
h2. Exemplu
| catun.in | catun.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="catun") ==
table(example). |_. catun.in |_. catun.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 |
==Include(page="template/taskfooter" task_id="catun")==
