1. 문제 설명

플로이드

2. 문제 분석

각 노드에서 다른 모든 노드에 대한 최단 거리를 찾고 싶다면 플로이드-워셜 알고리즘을 사용하자. 시간 복잡도가 큐브라는 데 주의.

3. 나의 풀이

import Foundation

let N = Int(readLine()!)!
let M = Int(readLine()!)!
let INF = Int.max
var nodes = Array(repeating: Array(repeating: INF, count: N+1), count: N+1)
for i in 1..<N+1{
    nodes[i][i] = 0
}
for _ in 0..<M{
    let input = readLine()!.split(separator: " ").map({Int(String($0))!})
    let (node1, node2, cost) = (input[0], input[1], input[2])
    if nodes[node1][node2] > cost{
        nodes[node1][node2] = cost
    }
}

for k in 1..<N+1{
    for i in 1..<N+1{
        for j in 1..<N+1{
            if nodes[i][k] == INF || nodes[k][j] == INF{
                continue
            }
            if nodes[i][j] > nodes[i][k] + nodes[k][j]{
                nodes[i][j] = nodes[i][k] + nodes[k][j]
            }
        }
    }
}

for i in 1..<N+1{
    for j in 1..<N+1{
        if nodes[i][j] == INF{
            nodes[i][j] = 0
        }
    }
}

for i in 1..<N+1{
    for j in 1..<N+1{
        print(nodes[i][j], terminator: " ")
    }
    print()
}