on
11657. 타임머신 (Swift, Python)
11657. 타임머신 (Swift, Python)
let INF: Int = Int ( 1e9 ) // 무한을 나타내는 INF 상수
typealias nodeGraph = (nextNode: Int , cost: Int ) // graph에 사용할 typealias
// 벨만 포드 알고리즘
func bf(_ start: Int ) - > Bool {
dist[start] = 0
for i in 1. ..N {
for cur in 1. ..N {
for g in graph[cur] {
if dist[cur] ! = INF & & dist[g.nextNode] > dist[cur] + g.cost {
dist[g.nextNode] = dist[cur] + g.cost
// N번째에서 최단 거리가 갱신되는 경우는 음수 사이클이 있음을 나타낸다.
if i = = N {
return true
}
}
}
}
}
return false
}
var N: Int = 0
var M: Int = 0
if let input = readLine() {
let inputs = input.split(separator: " " ).map { Int ($0) ! }
N = inputs[ 0 ]
M = inputs[ 1 ]
}
var graph: [[nodeGraph]] = Array(repeating: [], count: N + 1 )
var dist: [ Int ] = Array(repeating: INF, count: N + 1 )
for _ in 0. . < M {
if let input = readLine() {
let inputs = input.split(separator: " " ).map { Int ($0) ! }
let a: Int = inputs[ 0 ]
let b: Int = inputs[ 1 ]
let c: Int = inputs[ 2 ]
graph[a].append((b, c))
}
}
let negativeCycle: Bool = bf( 1 )
if negativeCycle {
print ( "-1" )
} else {
for i in 2. ..N {
if dist[i] = = INF {
print ( "-1" )
} else {
print (dist[i])
}
}
}
from http://one10004.tistory.com/86 by ccl(A) rewrite - 2021-11-14 22:00:23