글 읽기 - 게시판 반례 모두 확인했는데 어디서 틀렸는지 잘 모르겠습니다.

tigger97 3년 전 0

게시판에 있는 반례를 모두 확인해봤는데 틀렸다고 나옵니다.

23%에서 틀리다고 나오는데 제가 어느 부분을 놓치고 있는건가요?

다익스트라가 처음이여서 그런지 좀 부족하네요.

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()

    data class Node(val start: Int, val dest: Int, val cost: Int) : Comparable<Node> {
        override fun compareTo(other: Node): Int = cost - other.cost // cost순으로 정렬
    }

    val n = br.readLine().toInt()
    val m = br.readLine().toInt()
    val pq = PriorityQueue<Node>()
    val arr = Array(n + 1) { Stack<Node>() }
    val distArr = IntArray(n + 1) { 987654321 } // 초기 cost를 무한대로 잡는다
    val visited = BooleanArray(n + 1) { false }
    for (i in 0 until m) {
        val (start, dest, cost) = br.readLine().split(' ').map { it.toInt() }
        arr[start].add(Node(start, dest, cost))
    }
    val (startCity, destCity) = br.readLine().split(' ').map { it.toInt() }
    distArr[startCity] = 0 // 시작 위치 0으로 초기화
    visited[startCity] = true // 첫 도시 방문 표시
    for (i in arr[startCity].indices) {
        pq.add(arr[startCity][i])
    }

    //다익스트라 시작
    while (pq.isNotEmpty()) {
        val temp = pq.poll()
        visited[temp.dest] = true // 방문 표시
        if (distArr[temp.dest] > distArr[temp.start] + temp.cost ) { // 만약 기존에 있던 값보다 temp.cost가 더 작다면 값 갱신
            distArr[temp.dest] = distArr[temp.start] + temp.cost
            for (i in arr[temp.dest].indices) { // 방문한 노드의 연결된 인덱스들 모두 pq에 추가
                if (!visited[arr[temp.dest][i].dest]) {
                    pq.add(arr[temp.dest][i])
                }
            }
        }
//        for (i in arr[temp.dest].indices) { // 방문한 노드의 연결된 인덱스들 모두 pq에 추가
//            if (!visited[arr[temp.dest][i].dest]) {
//                pq.add(arr[temp.dest][i])
//            }
//        }
    }
    println(distArr[destCity])
}

slah007 3년 전 0

최대 버스 수 * 비용 = 10^10이기 때문에 987654321이 충분히 큰 무한대 값이 아닙니다.

또한 10^10은 32bit 정수(int)로 표현이 안되는 범위인데 제가 java를 잘 몰라서 val만 쓰면 알아서 더 큰 자료형을 써주는지 모르겠네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

게시판 반례 모두 확인했는데 어디서 틀렸는지 잘 모르겠습니다.

tigger97 3년 전 0

slah007 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말