글 읽기 - 예제와 게시판에 있는 테스트케이스도 잘 되는데 오답이라고 나오네요

zkzkdhrkffo 3년 전 0

예제와 게시판에 있는 테스트케이스를 찾아서 돌려봤는데, 잘 나오는데

제출하면 오답이라고 나오네요

어디가 틀린걸까요..

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

public class Main {
   static int start,end;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        Graph g = new Graph(sc.nextInt());
        int m = sc.nextInt();
        for(int i = 0 ; i<m; i++) {
           int num1 = sc.nextInt();
           int num2 = sc.nextInt();
           int num3 = sc.nextInt();
           g.input(num1, num2, num3);
        }
        start = sc.nextInt();
        end = sc.nextInt();
        g.dijkstra(start,end);
    }
}

class Graph{
    private int n;           //노드들의 수
    private int maps[][];    //노드들간의 가중치 저장할 변수
 
    public Graph(int n){
        this.n = n;
        maps = new int[n+1][n+1];
         
    }
    public void input(int i,int j,int w){
    	if(maps[i][j] != 0 && maps[i][j] < w)
    		return;
        maps[i][j] = w;
    }
 
    public void dijkstra(int start, int end){
        long distance[] = new long[n+1];          //최단 거리를 저장할 변수
        boolean[] check = new boolean[n+1];     //해당 노드를 방문했는지 체크할 변수
         
        //distance값 초기화.
        for(int i=1;i<n+1;i++){
            distance[i] = Integer.MAX_VALUE;
        }

        //시작노드값 초기화.
        distance[start] =0;
        check[start] =true;
         
        //연결노드 distance갱신
        for(int i=1;i<n+1;i++){
            if(!check[i] && maps[start][i] !=-1){
                distance[i] = maps[start][i];
            }
        }
         
        for(int a=0;a<n-1;a++){
            long min=Integer.MAX_VALUE;
            int min_index=0;
             
            //최소값 찾기
            for(int i=1;i<n+1;i++){
                if(!check[i] && distance[i]!=0){
                    if(distance[i]<min ){
                        min=distance[i];
                        min_index = i;
                    }
                }
            }
             
            check[min_index] = true;
            for(int i=1;i<n+1;i++){
                if(!check[i] && maps[min_index][i]!=0){
                    if(distance[i] == 0)
                    	distance[i] = distance[min_index]+maps[min_index][i];
                    
                	if(distance[i]>distance[min_index]+maps[min_index][i]){
                        distance[i] = distance[min_index]+maps[min_index][i];
                    }
                }
            } 
        }
        System.out.println(distance[end]);
    }
}

herdson 3년 전 0

0 1 1 1 4 
4

올리신 코드로 예제 돌려보니까 출력이 이렇게 나오네용

zkzkdhrkffo 3년 전 0

앗, 죄송합니다ㅜㅜ

디버깅해보려고 써놓은 코드 빼는 걸 깜빡했네요ㅜ

수정했습니다..

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

문제

문제

출처

ICPC

예제와 게시판에 있는 테스트케이스도 잘 되는데 오답이라고 나오네요

zkzkdhrkffo 3년 전 0

herdson 3년 전 0

zkzkdhrkffo 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말