11404 swift - 플로이드

플로이드 워셜 알고리즘 사용

[그래프] 플로이드 워셜(Floyd-Warshall Algorithm)

중간노드를 거쳐서 갈 수 있는 경우를 고려하여 3중 for문으로 코드를 작성합니다.

import Foundation

var n = Int(readLine()!)!
var cost = Array(repeating: Array(repeating: 987654321, count: n), count: n)
for _ in 0..<Int(readLine()!)! {
    let abc = readLine()!.split{$0==" "}.map{Int(String($0))!}
    let (a, b, c) = (abc[0], abc[1], abc[2])
    cost[a-1][b-1] = min(c, cost[a-1][b-1])
}

for k in 0..<n {
    for i in 0..<n {
        for j in 0..<n {
            if (i==j) { cost[i][j] = 0 }
            cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])
        }
    }
}

for result in cost {
    let validator = result.map { $0 == 987654321 ? 0 : $0 }
    print(validator.map{String($0)}.joined(separator: " "))
}