글 읽기 - 다익스트라 사소한 차이인데 정답이 다릅니다.

ktj7916 4년 전 0

두 소스코드 모두 우선순위큐를 사용하였고

첫번째 소스코드는

start와 연결되어있는 정점과 가중치를 넣고시작하였고

두번째소스코드는

시작점과 가중치 0(자신에서자신이니까)를 넣었습니다

두 소스코드의 차이는 이것밖에없는데 첫번째는 70%에서 틀렸다고나오고

두번쨰는 통과가됩니다. 차이가없어보이는데 ㅠㅠ

두소스코드의 차이가뭔지 알려주실 고수분구합니다 ㅠㅠ

//<2번째소스코드>
import java.util.*;
import java.io.*;
public class Main
{
	public static int Vertex=0,Edge=0;
	public static ArrayList<List>[] Map;
	public static int[] dist;
	public static void main(String[] args)throws IOException 
	{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		Vertex=Integer.parseInt(st.nextToken());Edge=Integer.parseInt(st.nextToken());
		int start = Integer.parseInt(br.readLine()),i=0,v1=0,v2=0,distance=0;
		Map = new ArrayList[Vertex+1];
		dist= new int[Vertex+1];
		
		for(i=1;i<=Vertex;i++)
		{	
			Map[i]=new ArrayList<>();
			dist[i] = Integer.MAX_VALUE-1;
		}
		for(i=0;i<Edge;i++)
		{
			st=new StringTokenizer(br.readLine()," ");
			v1=Integer.parseInt(st.nextToken());
			v2=Integer.parseInt(st.nextToken());
			distance=Integer.parseInt(st.nextToken());
			Map[v1].add(new List(v2,distance));
		}
		Djikstra(start);
		for(i=1;i<=Vertex;i++)
		{	
			if(dist[i] != Integer.MAX_VALUE-1)
				System.out.println(dist[i]);
			else
				System.out.println("INF");
		}
	}
	public static void Djikstra(int start)
	{
		int i=0,now=0,now_dist=0,next=0,next_dist=0;
		PriorityQueue<List> pq = new PriorityQueue<>();
		dist[start]=0;
		pq.add(new List(start,0));
		while(!pq.isEmpty())
		{
			List temp = pq.poll();
			now=temp.index;
			now_dist=dist[now];
			
			for(i=0;i<Map[now].size();i++)
			{
				next=Map[now].get(i).index;
				next_dist=Map[now].get(i).dist+now_dist;
				if(dist[next]>next_dist)
				{
					dist[next]=next_dist;
					pq.add(new List(next,dist[next]));
				}
			}
		}
	}
}
class List implements Comparable<List>
{
	int index=0;
	int dist=0;
	List(int index,int dist)
	{
		this.index=index;
		this.dist=dist;
	}
	public int compareTo(List o)
	{
		return this.dist<=o.dist?-1:1;
	}
}




//<첫번째소스코드>
import java.util.*;
import java.io.*;
public class Main
{
	public static int Vertex=0,Edge=0;
	public static ArrayList<List>[] Map;
	public static int[] dist;
	public static void main(String[] args)throws IOException 
	{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		Vertex=Integer.parseInt(st.nextToken());Edge=Integer.parseInt(st.nextToken());
		int start = Integer.parseInt(br.readLine()),i=0,v1=0,v2=0,distance=0;
		Map = new ArrayList[Vertex+1];
		dist= new int[Vertex+1];
		
		for(i=1;i<=Vertex;i++)
		{	
			Map[i]=new ArrayList<>();
			dist[i] = Integer.MAX_VALUE-1;
		}
		for(i=0;i<Edge;i++)
		{
			st=new StringTokenizer(br.readLine()," ");
			v1=Integer.parseInt(st.nextToken());
			v2=Integer.parseInt(st.nextToken());
			distance=Integer.parseInt(st.nextToken());
			Map[v1].add(new List(v2,distance));
		}
		Djikstra(start);
		for(i=1;i<=Vertex;i++)
		{	
			if(dist[i] != Integer.MAX_VALUE-1)
				System.out.println(dist[i]);
			else
				System.out.println("INF");
		}
	}
	public static void Djikstra(int start)
	{
		int i=0,now=0,now_dist=0,next=0,next_dist=0;
		PriorityQueue<List> pq = new PriorityQueue<>();
		
		dist[start]=0;
		for(i=0;i<Map[start].size();i++)
		{	
			now=Map[start].get(i).index;
			now_dist=Map[start].get(i).dist;
			
			dist[now]=now_dist;
			pq.add(new List(now,dist[now]));
		}
		while(!pq.isEmpty())
		{
			List temp = pq.poll();
			now=temp.index;
			now_dist=dist[now];
			
			for(i=0;i<Map[now].size();i++)
			{
				next=Map[now].get(i).index;
				next_dist=Map[now].get(i).dist+now_dist;
				if(dist[next]>next_dist)
				{
					dist[next]=next_dist;
					pq.add(new List(next,dist[next]));
				}
			}
		}
	}
}
class List implements Comparable<List>
{
	int index=0;
	int dist=0;
	List(int index,int dist)
	{
		this.index=index;
		this.dist=dist;
	}
	public int compareTo(List o)
	{
		return this.dist<=o.dist?-1:1;
	}
}

djm03178 4년 전 1

https://ideone.com/GCKvSg

ktj7916 4년 전 0

진짜 감사합니다 ㅠㅠㅠㅠ 똑같은 정점에 여러개가연결될수있다는걸 생각못했네요 정말갑사합니다 ㅠ

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

문제

문제

출처

ICPC

다익스트라 사소한 차이인데 정답이 다릅니다.

ktj7916 4년 전 0

djm03178 4년 전 1

ktj7916 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말