문제

링크https://www.acmicpc.net/problem/11404

풀이

모든 도시의 쌍에 가는데 필요한 비용의 최솟값을 출력해봐라가
이문제의 핵심이고
이는 기본적인 플로이드 워셜 알고리즘으로 해결가능하다.

입력
첫째 줄에 도시의 개수 N이 주어지고
둘째 줄에 버스의 개수 m이 주어진다.
셋째 줄부터 m+2줄까지 버스의 정보가 주어지는데
a, b, c순으로 주어지고 a는 시작도시 b는 도착도시 c는 필요한 비용이다.

시작도시와 도착도시를 연결하는 노선은 하나가 아닐 수 있고
-> 이는 방향 그래프라는 점을 알 수 있다.
또한 조건으로 자기자신으로 가는 버스는 없고
a에서 b로가는 간선이 하나가 아닐 수 있다.
-> 이조건에 눈길이 가는데 간선이 여러개 일 수 도 있다는 뜻이다.

그런데 이 문제에서는 어차피 최소비용만을 구하면되므로
여러개의 간선중 최소 비용의 간선으로 대표간선으로 두고
다른 비용의 간선을 다룰 필요가 없다.

코드

import sys

input = sys.stdin.readline
INF = int(1e9)

N = int(input().rstrip())
M = int(input().rstrip())

distance = [[INF] * (N+1) for _ in range(N+1)]

#자기자신으로 가는비용 0으로 갱신
for i in range(1, N+1):
  distance[i][i] = 0
  
for _ in range(M):
  a, b, c = map(int, input().split())
  
  if(distance[a][b] > c):
    distance[a][b] = c

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


#출력
for i in range(1, N+1):
  for j in range(1, N+1):
    if(distance[i][j] < INF):
      print(distance[i][j], end = ' ')
    else:
      print(0, end = ' ')
  print()

다른 코드들을 보고난 후

내코드에서 크게 수정할 부분은 없고
굳이 찾자면 여러번을 반복해서 입력받는 것이아니면 그냥
sys.stdin.readline으로 받는것이아니라 input함수로 받아도 좋을것같다.