백준 특정한 최단 경로

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

방향성이 없고, 두 정점 사이 간선이 최대 1개인 그래프에서 1번 정점에서 N번 정점까지 v1, v2 두 정점을 거치며 이동하는 최단 거리를 구하는 문제이다.

단순하게 다익스트라 알고리즘을 사용하는 문제이다.

'1번 정점 - v1 - v2 - N번 정점' 또는 '1번 정점 - v2 - v1 - N번 정점' 경로만 찾아보면 된다.

따라서 각 정점에서 다익스트라를 사용하면 되는데, 잘 생각해보면 케이스 당 2번의 다익스트라를 사용하면 된다.

'1번 정점 - v1 - v2 - N번 정점' 경로에선, v1에서의 다익스트라를 통해 1 - v1과 v1 - v2경로를 알 수 있고 v2에서의 다익스트라를 통해 v2 - N을 알 수 있다.

두 번째 케이스도 마찬가지이다.

단 여기서 경로가 없는 경우에 대해서 체크가 필요하다.

위처럼 경로가 주어지고, v1 = 2, v2 = 3인 경우를 생각해보자.

1 - 2 - 3 - 4 경로를 찾는 케이스에서는
2번에서 다익스트라를 통해 2 - 1 경로와 2 - 3경로, 3번에서 다익스트라를 통해 3 - 4 경로의 최단 거리를 구할 수 있다.

하지만, 2 - 1경로와 3 - 4경로는 존재하지 않아 INF값이 나온다.

그리고 극단적으로, 2번과 3번을 연결하는 간선마저 없다면 세 경로의 최단 거리가 모두 INF값이 나오게 된다.

따라서 경로가 없음을 판단할 경우, 각 경로마다 INF값이 있는지 확인해봐야 한다.

(처음에 단순히 cost 합의 오버플로우 발생 여부만을 가지고 경로없음을 판단하다 INF가 두 개 더해질 경우 정상처럼 보이는 값이 나왔었다)

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val (N, E) = readLine().split(' ').map{it.toInt()}
    val links = Array(N + 1){LinkedList<Stop>()}

    for(i in 1..E){
        val (a, b, c) = readLine().split(' ').map{it.toInt()}
        links[a].add(Stop(b,c))
        links[b].add(Stop(a,c))
    }

    val (must1, must2) = readLine().split(' ').map{it.toInt()}

    var answer = -1
    fun dijkstra(start: Int): IntArray{
        val pq = PriorityQueue<Stop>{s1, s2 -> s1.cost - s2.cost}
        val dest = IntArray(N + 1){ Int.MAX_VALUE }
        val visited = BooleanArray(N + 1){false}
        dest[start] = 0

        pq.offer(Stop(start, 0))
        while(pq.isNotEmpty()){
            val next = pq.poll()
            if(visited[next.n]) continue
            visited[next.n] = true

            for(s in links[next.n]){
                val cost = next.cost + s.cost

                if(dest[s.n] > cost){
                    dest[s.n] = cost
                    pq.offer(Stop(s.n, cost))
                }
            }
        }
        return dest
    }

    val dijk1 = dijkstra(must1)
    val dijk2 = dijkstra(must2)

    val startToMust1 = dijk1[1]
    val must1ToMust2 = dijk1[must2]
    val must2ToDest = dijk2[N]

    val startToMust2 = dijk2[1]
    val must2ToMust1 = dijk2[must1]
    val must1ToDest = dijk1[N]

    var route1Cost = startToMust1 + must1ToMust2 + must2ToDest
    var route2Cost = startToMust2 + must2ToMust1 + must1ToDest

    if(listOf(startToMust1, must1ToMust2, must2ToDest).contains(Int.MAX_VALUE)) route1Cost = Int.MAX_VALUE
    if(listOf(startToMust2, must2ToMust1, must1ToDest).contains(Int.MAX_VALUE)) route2Cost = Int.MAX_VALUE

    answer = if(route1Cost > route2Cost) route2Cost else route1Cost

    if(answer == Int.MAX_VALUE) answer = -1
    print(answer)
}

data class Stop(
    val n: Int,
    val cost: Int
)