on
1738. 골목길 (Swift, Python)
1738. 골목길 (Swift, Python)
typealias graphElement = (node: Int , cost: Int )
let nINF: Int64 = Int64(Int32.min)
// 벨만 포드 알고리즘
func bf(_ start: Int ) {
dist[start] = 0
for i in 0. . < n {
for cur in 1. ..n {
for g in graph[cur] {
let nextNode: Int = g.node
let cost: Int = g.cost
let nextCost: Int64 = dist[cur] + Int64(cost)
if dist[cur] ! = nINF & & dist[nextNode] < nextCost {
dist[nextNode] = nextCost
route[nextNode] = cur // next 노드로 가는 전 node를 담아줌
if i = = n - 1 {
dist[nextNode] = Int64(Int32.max) // 도착 노드의 금품을 무한으로 설정
}
}
}
}
}
}
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: [[graphElement]] = Array(repeating: [graphElement](), count: n + 1 )
var dist: [Int64] = Array(repeating: nINF, count: n + 1 ) // 시작 지점에서 node까지의 최대 금품
var route: [ Int ] = Array(repeating: 0 , count: n + 1 ) // 경로를 담아주기 위한 배열
var u: Int = 0
var v: Int = 0
var w: Int = 0
for _ in 0. . < m {
if let input = readLine() {
let inputs = input.split(separator: " " ).map { Int ($0) ! }
u = inputs[ 0 ]
v = inputs[ 1 ]
w = inputs[ 2 ]
graph[u].append((v, w))
}
}
bf( 1 )
var res: [ Int ] = [n] // 최적의 경로를 담아줄 결과 배열
if dist[n] = = Int32.max { // n번 노드로 가는데 사이클이 포함되어 있을 경우 -1 출력
print ( "-1" )
} else { // n번 노드로 가는데 사이클이 포함되어 있지 않을 경우
var node: Int = n
// n번부터 역으로 res 배열에 담아준다.
while node ! = 1 {
node = route[node]
res.append(node)
}
// 뒤집어서 출력
for i in res.reversed() {
print (i, terminator: " " )
}
}
from http://one10004.tistory.com/91 by ccl(A) rewrite - 2021-11-18 03:01:31