PROBLEMA 5: Diagrame Voronoi pe grafuri
DEADLINE: Duminica, 28 februarie 1999
DOMENIU: Drumuri in grafuri
TIMP DE IMPLEMENTARE: 1h 30'
PUNCTAJ: 75 dexteri
Intr-un regat feudal exista mai multe asezari omenesti, 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.
Observatii:
1) Asezarile sunt numerotate de la 1 la N.
1) Daca un catun este la distanta egala (minima) intre doua fortarete,
el va fi aservit fortaretei cu numarul de ordine minim.
2) Daca un catun nu are drum catre nici o fortareata, el va ramane
independent.
DATELE DE INTRARE: Fisierul ASEZARI.IN contine datele:
N M K - numarul de asezari, de drumuri si de fortarete
F1 F2 ... FK - numerele de ordine ale fortaretelor
X1 Y1 D1 \ - drumurile imperiului, unde Xi Yi Di semnifica
... > ca exista un drum de lungime Di intre
XM YM DM / asezarile Xi si Yi
Restrictii: N<=180 (ghiciti de unde si pana unde :) ),
1<=K<=N
1<=Di<=1000, Di sunt numere naturale
DATELE DE IESIRE: Fisierul ASEZARI.OUT va contine un vector V cu N
elemente, unde
/ 0, daca asezarea i este fortareata sau catun independent
V[i]= <
\ numarul fortaretei de care se leaga catunul i, altfel
Elementele vectorului V se vor tipari pe o singura linie, separate
prin spatii.
EXEMPLU:
ASEZARI.IN ASEZARI.OUT
8 9 2 5 0 5 0 0 5 0 2
2 5
1 3 6 (cu semnificatia ca:
1 5 3 - domeniul lui 2 se compune din 8
1 6 1 - domeniul lui 5 se compune din 1, 3 si 6
2 3 8 - catunele 4 si 7 sunt independente)
5 6 5
6 8 7
3 6 2
4 7 1000
2 8 5
COMPLEXITATE RECOMANDATA: O(N^2).
Indicatie de ultima ora - cred ca se intelege ca in Evul Mediu toate
drumurile erau cu dublu sens! :)
|
|
