글 읽기 - 18%쯤에 틀렸다고 나옵니다ㅠㅠ 어디서 잘못된 걸까요?

imds39 6년 전 0

18%쯤에서 계속 틀립니다!!ㅠㅠ

어디서 틀린건지 모르겠네요...ㅠㅠ 도와주세요!

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(System.in);

        final int INF = 9999;
        int numOfNode = sc.nextInt() + 1;
        int numOfBus = sc.nextInt();

        int[][] adjInfo = new int[numOfNode][numOfNode];
        int[] shortestDistance = new int[numOfNode];
        boolean[] visited = new boolean[numOfNode];
        for (int i = 0; i < numOfNode; i++) {
            shortestDistance[i] = INF;
            visited[i] = false;
            for (int j = 0; j < numOfNode; j++) {
                adjInfo[i][j] = (i == j) ? 0 : INF;
            }
        }

        for (int i = 0; i < numOfBus; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();
            int distance = sc.nextInt();
            if (adjInfo[start][end] > distance) {
                adjInfo[start][end] = distance;
            }
        }

        int source = sc.nextInt();
        int destination = sc.nextInt();

        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(source);
        shortestDistance[source] = 0;

        while (!q.isEmpty()) {
            int curIndex = q.poll();
            if (!visited[curIndex]) {
                visited[curIndex] = true;

                for (int adjIndex = 1; adjIndex < numOfNode; adjIndex++) {
                    if (!visited[adjIndex]) {
                        int newDis = shortestDistance[curIndex] + adjInfo[curIndex][adjIndex];
                        shortestDistance[adjIndex] = (newDis < shortestDistance[adjIndex]) ? newDis : shortestDistance[adjIndex];
                        q.offer(adjIndex);
                    }
                }
            }
        }

        System.out.println(shortestDistance[destination]);
    }
}

upple1 6년 전 0

INF값을 왜이리 적게 잡아줬나요? 비용 범위가 100000까지고 노드가 최대 1000개면 1억 이상은 잡아야 할텐데

imds39 6년 전 0

자답합니다

Queue를 PriorityQueue로 변경하였고, Visist배열과 visited체크 로직을 없애서 성공했습니다

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

문제

문제

출처

ICPC

18%쯤에 틀렸다고 나옵니다ㅠㅠ 어디서 잘못된 걸까요?

imds39 6년 전 0

upple1 6년 전 0

imds39 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말