0126 - D Max
Enunț
Se considerã un graf neorientat conex cu n
vârfuri, numerotate de la 1
la n
, şi m
muchii. Definim distanţa minimă între două noduri x
şi y
ca fiind numărul minim de muchii al unui lanţ elementar care uneşte x
cu y
.
Cerinţa
Sã se determine nodul aflat la cea mai mare distanţã minimă faţã de nodul 1
.
Date de intrare
Fişierul de intrare dmaxIN.txt
conţine pe prima linie două numere n
şi m
, reprezentând numărul de noduri, respectiv numărul de muchii. Fiecare dintre urmãtoarele m
linii va conţine câte două numere x
şi y
, separate printr-un spaţiu, cu semnificaţia: existã o muchie între nodul x
şi nodul y
.
Date de ieşire
Fişierul de ieşire dmaxOUT.txt
va conţine pe prima linie numărul z
, prin care este identificat nodul aflat la cea mai mare distanţã minimă faţã de nodul 1
.
Restricţii şi precizări
0 < n < 100
0 < m < 1000
- Dacă există mai multe noduri aflate la distanţa maximă, poate fi ales oricare dintre ele.
Exemplul 1
dmaxIN.txt
6 7 1 3 1 2 2 3 2 4 3 4 4 5 5 6
dmaxOUT.txt
6
Explicație
Nodul 6
se află la distanţa minimă 4
faţă de nodul 1
.
Exemplul 2
dmaxIN.txt
101 1001
dmaxOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
import heapq
def dijkstra(graf, start):
n = len(graf)
distante = [float('inf')] * n
distante[start - 1] = 0
heap = [(0, start)]
while heap:
distanta_curenta, nod_curent = heapq.heappop(heap)
if distanta_curenta > distante[nod_curent - 1]:
continue
for vecin in graf[nod_curent]:
distanta = distanta_curenta + 1
if distanta < distante[vecin - 1]:
distante[vecin - 1] = distanta
heapq.heappush(heap, (distanta, vecin))
return distante
def verificare_restrictii(n, m):
if 0 < n < 100 and 0 < m < 1000:
return True
return False
def main():
with open("dmaxIN.txt", "r") as fisier:
n, m = map(int, fisier.readline().split())
if not verificare_restrictii(n, m):
with open("dmaxOUT.txt", "w") as fisier_iesire:
fisier_iesire.write("Datele nu corespund restrictiilor impuse")
return
graf = {i: [] for i in range(1, n + 1)}
for _ in range(m):
x, y = map(int, fisier.readline().split())
graf[x].append(y)
graf[y].append(x)
distante = dijkstra(graf, 1)
nod_max_distanta = max(range(1, n + 1), key=lambda x: distante[x - 1])
with open("dmaxOUT.txt", "w") as fisier_iesire:
fisier_iesire.write(str(nod_max_distanta))
if __name__ == "__main__":
main()