백준 11657 타임머신
23 Jun 2021https://www.acmicpc.net/problem/11657
도시 간에 이동 가능한 버스 노선들이 주어졌을 때 1번 도시에서 나머지 도시로 가는 가장 빠른 시간을 구하는 문제이다. 가중치로는 음의 값을 가질 수 있기 때문에 다익스트라가 아닌 벨만포드나 플로이드를 사용해야 할 것이 예상된다.
그 중 한 도시에서 나머지로의 최단 경로를 찾는 문제이기 때문에 벨만포드를 사용해서 구하는 것이 좋다. 벨만포드의 경우 음의 가중치를 갖는 그래프가 현실에서는 많이 없기 때문에 시간과 관련된 문제가 나와서 과거로 돌아간다던지 하는 경우가 대부분이다.
문제 자체는 벨만포드 기본 알고리즘을 그대로 사용하면 되는 문제이기 때문에 어렵지 않게 구현할 수 있다. 음의 사이클이 나오는 경우를 고려해줘야 한다는 것만 유의하면 된다.
- 전체 코드
let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0], m = nm[1], INF = 60_000_001
var Dist:[Int] = Array(repeating: INF, count: n+1)
var Edge:[[(Int, Int)]] = Array(repeating: [], count: n+1)
for _ in 1...m {
let line = readLine()!.split(separator: " ").map{Int(String($0))!}
Edge[line[0]].append((line[1], line[2]))
}
Dist[1] = 0
for _ in 1..<n {
for i in 1...n {
if Dist[i] == INF {
continue
}
for e in Edge[i] {
Dist[e.0] = min(Dist[e.0], Dist[i] + e.1)
}
}
}
var change = false
for i in 1...n {
if Dist[i] == INF {
continue
}
for e in Edge[i] {
if Dist[e.0] > Dist[i] + e.1 {
change = true
break
}
}
}
if change {
print(-1)
}
else {
for i in 2...n {
print(Dist[i] == INF ? -1 : Dist[i])
}
}