백준 1916 최소비용 구하기

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

분류: 다익스트라

---

접근방식

전형적인 최단경로 문제였습니다. 다익스트라 알고리즘으로 해결할 수 있었습니다.

다익스트라 알고리즘을 알면 별도의 설명은 필요 없을듯 하네요.

다익스트라 포스팅을 한 번 해야겠습니다.. 

 

해결방법

let n = Int(readLine()!)!
var cities = [[(end: Int, value: Int)]](repeating: [], count: n+1)
for _ in 0..<Int(readLine()!)! {
    let d = readLine()!.split(separator: " ").map { Int(String($0))! }
    cities[d[0]].append((d[1], d[2]))
}

let se = readLine()!.split(separator: " ").map { Int(String($0))! }

var visited = [Bool](repeating: false, count: n+1)
visited[0] = true

var graph = [Int](repeating: Int.max, count: n+1)
graph[se[0]] = 0
visit(se[0])

func visit(_ current: Int) {
    guard current != se[1] else { return }
    
    visited[current] = true
    for (end, value) in cities[current] {
        graph[end] = min(graph[end], graph[current] + value)
    }
    
    let next = graph.enumerated()
        .filter({ !visited[$0.offset] })
        .min(by: { $0.element < $1.element })!.offset
    visit(next)
}

print(graph[se[1]])

 

배운점

무한으로 설정해두는 부분을 비용의 최대로 해버려서 몇 번 틀렸다..
한 경로의 비용이 100000이라는 건 충분히 더 커질 수 있다는건데 ... !!!