Dijkstra : 파티 [백준 1238, Kotlin]

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

 

[풀이]

n 명에 대한 다익스트라를 전부 해줌

cost → time으로 변경

x로 가는 최소 x에서 가는 최소의 합 구하기

[코드]

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.PriorityQueue
import kotlin.math.max

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val nmx = br.readLine().split(" ").map { it.toInt() }
    val n = nmx[0]
    val m = nmx[1]
    val x = nmx[2]
    val graph = List(n + 1) { mutableListOf<Pair<Int,Int>>() }
    for (i in 0 until m) {
        val input = br.readLine().split(" ").map { it.toInt() }
        graph[input[0]].add(Pair(input[1],input[2]))
    }

    val distance = MutableList(n+1){MutableList(n + 1) { Int.MAX_VALUE }}
    for(i in 1..n) {
        dijkstra(i, graph, distance[i])
    }
    var maxTime = 0

    for(i in 1 until n+1){
        if(i == x) {
            continue
        }
        val sum = distance[i][x] + distance[x][i]
        maxTime = max(sum,maxTime)
    }

    println(maxTime)
}

fun dijkstra(start: Int, graph: List<MutableList<Pair<Int,Int>>>, distance: MutableList<Int>) {

    //우선순위 큐에 저장 비용, 노드 순으로 저장
    val q = PriorityQueue<Pair<Int, Int>>{ p1, p2 -> p1.first - p2.first // 우선 순위 큐
        when {
            p1.first > p2.first -> 1
            p1.first < p2.first -> -1
            else -> 0
        }
    }
    q.add(Pair(0, start))
    distance[start] = 0

    while (q.isNotEmpty()) {
        val information = q.poll()
        val dist = information.first
        val now = information.second

        if (distance[now] < dist) {
            continue
        }

        for (i in 0 until graph[now].size) {
            val target = graph[now][i]
            val time = dist + target.second
            if (time < distance[target.first]) {
                distance[target.first] = time
                q.add(Pair(time, target.first))
            }
        }
    }
}

 

[출처]

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

1238번: 파티