백준 11404. 플로이드

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

플로이드 워셜 알고리즘만 알면 쉽게 풀 수 있는 문제

플로이드 워셜 알고리즘의 점화식
Dab = min(Dab, Dak + Dkb)

파이썬 코드

import sys
input = sys.stdin.readline

INF = int(1e9)

# 도시 개수 n
n = int(input())

# 버스 개수 m
m = int(input())

# 2차원 리스트(그래프 표현)을 만들고 모든 값을 무한으로 초기화
graph = [[INF] * (n+1) for _ in range(n+1)]

# 자기 자신에서 자신으로 가는 비용은 0으로 초기화
for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0

# 간선 입력
for _ in range(m):
    a, b, c = map(int, input().split())
    # 문제에서 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다고
    # 명시했으니 더 작은 값으로 설정
    graph[a][b] = min(graph[a][b], c)

# 플로이드 워셜 알고리즘 수행
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행 결과 출력
for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b] == INF:
            print("0", end=" ")
        else:
            print(graph[a][b], end=" ")
    print()

자기 자신에서 자신으로 가는 값을 0으로 초기화하는 반복문을 지우고 플로이드 워셜 알고리즘 수행 때 if 문을 넣어주면 더 짧고 빠르다.
단축 코드

import sys
input = sys.stdin.readline

INF = int(1e9)

# 도시 개수 n
n = int(input())

# 버스 개수 m
m = int(input())

# 2차원 리스트(그래프 표현)을 만들고 모든 값을 무한으로 초기화
graph = [[INF] * (n+1) for _ in range(n+1)]

# 간선 입력
for _ in range(m):
    a, b, c = map(int, input().split())
    # 문제에서 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다고
    # 명시했으니 더 작은 값으로 설정
    graph[a][b] = min(graph[a][b], c)

# 플로이드 워셜 알고리즘 수행
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            if a == b:
                graph[a][b] = 0
            else:
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행 결과 출력
for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b] == INF:
            print("0", end=" ")
        else:
            print(graph[a][b], end=" ")
    print()