백준 17396번
https://www.acmicpc.net/problem/17396

문제

---

생각하기

---

• 다익스트라 문제이다.

  • 양방향 그래프 문제이다.

• N-1 노드를 제외하고 보이는 곳은 갈 필요가 없으므로 굳이 방문하지 않았다.

• dist배열의 N-1 노드의 값을 정답으로 하면 된다.

  • dist배열의 N-1의 값이 Long.MAXVALUE일 경우

동작

코드

---

Kotlin

import java.io.*
import java.util.*


// input
private lateinit var br: BufferedReader

// variables
private var N = 0 // 분기점의 수
private var M = 0 // 분기점들을 잇는 길의 수
private var ans = 0
private const val INF = Long.MAX_VALUE

private lateinit var isShowingArr: IntArray
private lateinit var adjList: MutableList<MutableList<Node>>
private lateinit var dist: LongArray

private data class Node(
    var nodeNum: Int,
    var time: Long
) : Comparable<Node> { // End of compare
    override fun compareTo(other: Node): Int {
        return time compareTo other.time
    }
} // End of Node class

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val sb = StringBuilder()

    // input
    input()

    dijkstra(0)

    if (dist[N - 1] == Long.MAX_VALUE) {
        sb.append(-1)
    } else {
        sb.append(dist[N - 1])
    }

    bw.write(sb.toString())
    bw.close()
} // End of main

private fun dijkstra(startNodeNum: Int) {
    val isVisited = BooleanArray(N)
    val pq = PriorityQueue<Node>()
    dist = LongArray(N) { INF }

    dist[startNodeNum] = 0
    pq.offer(Node(startNodeNum, 0))

    while (pq.isNotEmpty()) {
        val pollNode = pq.poll()
        val pollStartNodeNum = pollNode.nodeNum
        if (isShowingArr[pollStartNodeNum] == 1 && pollStartNodeNum != N - 1) continue

        if (!isVisited[pollStartNodeNum]) {
            isVisited[pollStartNodeNum] = true

            val size = adjList[pollStartNodeNum].size
            for (i in 0 until size) {
                val nextNodeNum = adjList[pollStartNodeNum][i]
                if (!isVisited[nextNodeNum.nodeNum] && dist[nextNodeNum.nodeNum] > (dist[pollStartNodeNum] + nextNodeNum.time)) {
                    dist[nextNodeNum.nodeNum] = dist[pollStartNodeNum] + nextNodeNum.time
                    pq.offer(Node(nextNodeNum.nodeNum, dist[nextNodeNum.nodeNum]))
                }
            }
        }
    }

} // End of dijkstra

private fun input() {
    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()

    adjList = ArrayList()
    for (i in 0..N) {
        adjList.add(ArrayList())
    }

    isShowingArr = IntArray(N)
    st = StringTokenizer(br.readLine())
    for (i in 0 until N) {
        isShowingArr[i] = st.nextToken().toInt()
    }

    for (i in 0 until M) {
        st = StringTokenizer(br.readLine())
        val a = st.nextToken().toInt() // a 분기점
        val b = st.nextToken().toInt() // b 분기점
        val t = st.nextToken().toLong() // 걸리는 시간

        adjList[a].add(Node(b, t))
        adjList[b].add(Node(a, t))
    }
} // End of input