4161 - Picard

Cerința

În galaxia noastră sunt n planete, numerotate de la 1 la n. Între unele dintre ele sunt calculate și cunoscute salturi warp bidirecționale de durate cunoscute, existând în total m astfel de salturi warp. Prin aceste salturi warp se asigură posibilitatea de navigare între oricare două planete, direct sau prin intermediul mai multor salturi warp intermediare. Flota stelară folosește foarte eficient aceste salturi pentru a naviga între planete, adică folosește trasee formate din unul sau mai multe salturi warp astfel încât durata obținută ca sumă a duratelor salturilor warp componente să fie întotdeauna minimă pentru oricare pereche de planete.

Proaspăt pensionat din Flota stelară, sătul de ferenghi și romulani, Jean Luc Picard dorește să se retragă pe o planetă cât mai izolată, adică o planetă pentru care suma duratelor salturilor warp folosite de Flota stelară de la ea la toate celelaltele planete din galaxie să fie maximă. Determinați planetele pe care se poate retrage Picard pentru a obține liniștea dorită. Dacă sunt mai multe planete care pot fi alese, acestea se vor afișa în ordine crescătoare a numerotării și separate prin câte un spațiu.

Date de intrare

Fișierul de intrare picard.in conține pe prima linie numerele n m, iar următoarele m linii câte trei numere i j L, cu semnificatia: între planetele i și j există un salt warp bidirecțional de durată L.

Date de ieșire

Fișierul de ieșire picard.out va conține planetele cerute în ordine crescătoare a numerotării și separate prin câte un spațiu.

Restricții și precizări

• 1 ≤ n ≤ 100
• durata oricărui salt este număr întreg din intervalul [1,1000]

Exemplu:

picard.in

6 9
1 3 5
1 4 5
1 5 4
2 3 5
2 4 1
2 5 2
3 6 2
4 6 4
5 6 4

picard.out

1

Explicație

Sumele duratelor minime de la fiecare planetă la toate celelale sunt:
De la planeta 1 la toate celelalte: 27 
De la planeta 2 la toate celelalte: 19 
De la planeta 3 la toate celelalte: 24 
De la planeta 4 la toate celelalte: 19 
De la planeta 5 la toate celelalte: 19 
De la planeta 6 la toate celelalte: 22
Prin urmare, Jean Luc Picard alege planeta 1.

Rezolvare

<syntaxhighlight lang="python3"> def floyd_warshall(n, distances):

   for k in range(1, n + 1):
       for i in range(1, n + 1):
           for j in range(1, n + 1):
               distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])

def find_max_distance(n, distances):

   max_sum = 0
   max_planets = []

   for i in range(1, n + 1):
       current_sum = sum(distances[i][1:])
       if current_sum > max_sum:
           max_sum = current_sum
           max_planets = [i]
       elif current_sum == max_sum:
           max_planets.append(i)

   return max_planets

if __name__ == "__main__":

   with open("picard.in", "r") as fin, open("picard.out", "w") as fout:
       n, m = map(int, fin.readline().split())
       distances = [[float('inf')] * (n + 1) for _ in range(n + 1)]
       
       for i in range(1, n + 1):
           distances[i][i] = 0

       for _ in range(m):
           i, j, L = map(int, fin.readline().split())
           distances[i][j] = distances[j][i] = L

       floyd_warshall(n, distances)
       max_planets = find_max_distance(n, distances)

       fout.write(" ".join(map(str, max_planets)))

</syntaxhighlight>