11404번: 플로이드


👉문제 링크


느낀점

  • 간단했다.
  • 플로이드 워셜 문제를 풀어보았다.
  • 세 개 점 중에서 제일 위에 있는 a는 경유지여야 한다(했다).
  • 세 개 점이 다르다는 것을 보장해야한다.

정답 코드 및 해설

N_city = int(input())
N_bus = int(input())

S_city = [[float('inf') for _ in range(N_city)] for __ in range(N_city)]

for bus in range(N_bus):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if c < S_city[a][b]:
        S_city[a][b] = c

for a in range(N_city):
    for b in range(N_city):
        if a != b:
            for c in range(N_city):
                if a != c and b != c:
                    temp_route = S_city[b][a] + S_city[a][c]
                    if temp_route < S_city[b][c]:
                        S_city[b][c] = temp_route

for a in range(N_city):
    for b in range(N_city):
        if S_city[a][b] == float('inf'):
            S_city[a][b] = 0

for a in S_city:
    print(" ".join(map(str, a)))

좋은 웹페이지 즐겨찾기