[백준/BOJ] 1956번: 운동

문제

https://www.acmicpc.net/problem/1956

1956번: 운동

해설

플로이드 와샬 알고리즘을 사용하여 해결할 수 있는 문제이다.

우선 초기값을 설정할 배열을 map이라 하자.

map을 INF(100000000)으로 초기화해주었다.

이후 플로이드 와샬 알고리즘을 수행하여 각 정점에서 각 정점까지의 최단 경로를 구해준다.

플로이드 와샬 알고리즘의 수행이 끝났다면, 사이클을 찾아야 한다.

map[i][j]와 map[j][i]가 모두 INF가 아니라면 사이클이 존재한다는 것이다.

따라서 도로의 길이의 합은 map[i][j] + map[j][i]가 되고, 이 값이 INF와 같다면 사이클이 없는 것이므로 -1을 출력하면 된다.

코드

private const val INF = 100000000
private lateinit var map: Array<IntArray>

fun main() = with(System.`in`.bufferedReader()) {
    val (v, e) = readLine().split(" ").map { it.toInt() }
    map = Array(v + 1) { IntArray(v + 1) { INF } }

    repeat(e) {
        val (start, end, dist) = readLine().split(" ").map { it.toInt() }
        map[start][end] = dist
    }

    floyd(v)

    var ans = INF
    for(i in 1 .. v) {
        for(j in 1 .. v) {
            if(i == j) continue
            if(map[i][j] != INF && map[j][i] != INF) {
                ans = minOf(ans, map[i][j] + map[j][i])
            }
        }
    }

    if(ans == INF) println(-1)
    else println(ans)
}

private fun floyd(n: Int) {
    for(k in 1 .. n) {
        for(i in 1 .. n) {
            for(j in 1 .. n) {
                map[i][j] = minOf(map[i][j], map[i][k] + map[k][j])
            }
        }
    }
}