백준 11404 플로이드

출처: www.acmicpc.net/problem/11404

분류: 플로이드 와샬

---

접근방식

이름처럼 전형적인 플로이드 와샬 문제였습니다.

플로이드 와샬 알고리즘을 알면 쉽게 풀 수 있었던 문제였네요!

플로이드 와샬이 익숙하지 않으시다면 여기로 :]

 

해결방법

let n = Int(readLine()!)!

var values = [[Int?]](repeating: [Int?](repeating: nil, count: n+1), count: n+1)

for i in 1...n {
    values[i][i] = 0
}

for _ in 0..<Int(readLine()!)! {
    let d = readLine()!.split(separator: " ").map { Int(String($0))! }
    values[d[0]][d[1]] = min(values[d[0]][d[1]] ?? Int.max, d[2])
}

for k in 1...n {
    for s in 1...n {
        for e in 1...n {
            guard k != s else { continue }
            if let startToK = values[s][k], let kToEnd = values[k][e] {
                values[s][e] = min(values[s][e] ?? Int.max, startToK + kToEnd)
            }
        }
    }
}

values.dropFirst().map { $0.dropFirst() }.forEach {
    print($0.map { String($0 ?? 0) }.joined(separator: " "))
}

 

배운점