백준 - 타임머신 (11657)

struct Edge {
    let start: Int
    let end: Int
    let time: Int
}

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (N, M) = (input[0], input[1])
var edges = [Edge]()
var distance = Array(repeating: Int.max, count: N+1)

// 에지 리스트 만들기
for _ in 0..<M {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    edges.append(Edge(start: input[0], end: input[1], time: input[2]))
}

// 벨만포드 알고리즘 수행
distance[1] = 0

for _ in 0..<N {
    for j in 0..<M {
        let now = edges[j]
        if distance[now.start] != Int.max && distance[now.end] > distance[now.start] + now.time {
            distance[now.end] = distance[now.start] + now.time
        }
    }
}

// 음수 사이클 확인
var isCycle = false

for i in 0..<M {
    let now = edges[i]
    if distance[now.start] != Int.max && distance[now.end] > distance[now.start] + now.time {
        isCycle = true
        break
    }
}

if !isCycle {
    for i in 2...N {
        print(distance[i] == Int.max ? "-1" : distance[i])
    }
} else {
    print("-1")
}

• 벨만포드 알고리즘을 적용하는 기본적인 문제