글 읽기 - [9370번]오답처리되는 원인이 무엇인지 모르겠습니다. 도움 부탁드립니다.

doo9012 5년 전 0

안녕하세요.

9370 문제에서 제출하자마자 틀렸다고 하는데요.. 원인을 모르겠습니다. 도움 부탁 드립니다.

import java.util.*;
public class Main 
{
	static int[][] map;
	static int[] dist;
	static boolean[] root;
	static ArrayList<Integer> goal = new ArrayList<Integer>();
	static int n,s,px,py;
	
	static int getmin(boolean[] mark)
	{
		int ret=-1, min=Integer.MAX_VALUE;
		for(int i=1; i<=n; i++)
		{
			if(!mark[i] && min>dist[i]) 
			{
				min=dist[i];
				ret=i;
			}
		}
		return ret;
	}
	
	static void dijkstra()
	{
		Arrays.fill(dist, 3000000);
		Arrays.fill(root, false);//경로를 찾기위한 배열
		boolean[] mark = new boolean[n+3];
		dist[s]=0;
		root[s]=false;
		int v=-1;
		while((v=getmin(mark))!=-1)
		{
			mark[v]=true;
			for(int i=1; i<=n; i++) 
			{
				if(!mark[i] && map[v][i]>0 && dist[i]>dist[v]+map[v][i])
				{
					dist[i]=dist[v]+map[v][i];
					
					if((v==px && i==py) || (v==py && i==px)) //거쳐야하는 부분을 거친 노드를 기록
					{
						root[i]=true;
					}
					else //직접적으로 거치지 않은 노드는 그 전 노드의 정보를 그대로 가져온다
					{
						root[i]=root[v];
					}
				}
			}
		}
	}
	
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		
		int T=sc.nextInt();
		
		while(T-- >0)
		{
			n=sc.nextInt();
			int m=sc.nextInt();
			int t=sc.nextInt();
			
			map = new int[n+3][n+3];
			dist= new int[n+3];
			root= new boolean[n+3];
			s=sc.nextInt();
			px=sc.nextInt();
			py=sc.nextInt();
			
			while(m-- >0)
			{
				int v1=sc.nextInt();
				int v2=sc.nextInt();
				int v3=sc.nextInt();
				
				if(map[v1][v2]==0 || map[v1][v2]>v3)
				{
					map[v1][v2]=v3;
					map[v2][v1]=v3;
				}
			}
			
			while(t-- >0)
			{
				goal.add(sc.nextInt()); //목적지를 ArrayList에 저장 
			}
			
			dijkstra();//다익스트라
			
			StringBuilder sb = new StringBuilder();
			for(int i=1; i<=n; i++)
			{
				boolean r=root[i];
				if(r && goal.contains((Object)i)) 
				{
					sb.append(i + " ");
				}
			}
			
			System.out.println(sb.toString());
			goal.clear();
		}
	}
}

sgchoi5 5년 전 2

BAPC 문제는 대회에서 사용했었던 TC (testdata) 가 공개되어 있습니다.

그거 잘 되는지 우선 해보세요.

http://gooddaytocode.blogspot....

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

문제

문제

출처

ICPC

[9370번]오답처리되는 원인이 무엇인지 모르겠습니다. 도움 부탁드립니다.

doo9012 5년 전 0

sgchoi5 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말