글 읽기 - [자바] 최단경로가 1개만 다르게 나와요...

billy1770 2년 전 0

후 ㅜㅜ

결과가

0
2
3
7

INF

이렇게 나와야하는데

0
2
3
6

INF

4번째 vertex만 거리가 다르게 나오네요 ㅜㅜㅜ 코드 계산해보면 7이 나와야 정상인데 뜬금없이 왜 6이 나올까요...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	static int distance[];
	static List<Edge>[] list;
	static int V,E,K;
	
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
	

		st = new StringTokenizer(br.readLine());
		
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		K = Integer.parseInt(br.readLine());
		
		distance = new int[V+1];
		Arrays.fill(distance, Integer.MAX_VALUE);
		
		
		list = new ArrayList[V+1];   //각각의 Vertex 정보
		
		
		for(int i = 1; i<=V; i++) {
			list[i]=new ArrayList<Edge>();  //Vertex들과 연결되어있는 엣지들의 모음
		}
		
		
		for(int i = 0; i<E; i++) {
		st = new StringTokenizer(br.readLine()," ");
		
		int u = Integer.parseInt(st.nextToken());
		int v = Integer.parseInt(st.nextToken());
		int w = Integer.parseInt(st.nextToken());
		
		list[u].add(new Edge(v,w));
		
		}
		
		dijkstra(K);
		
		for(int i = 1; i<=V; i++) {
			int result = distance[i];
			
			if(result == Integer.MAX_VALUE) {
				System.out.println("INF");
			}else {
			System.out.println(distance[i]);
			}
			}
	}
		
	
		private static void dijkstra(int start) { //우선순위 큐
			
			
			PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
			pq.add(new Edge(start, 0));
			distance[start]=0;
			
			while(pq.isEmpty()==false) {
				Edge edge = pq.poll();
				int currentNode = edge.vt;
				
				for(Edge e: list[currentNode]) {
					
					if(distance[e.vt]>distance[currentNode] + e.vt) {
						
						distance[e.vt] = distance[currentNode]+e.vt;
						pq.add(new Edge(e.vt, distance[e.vt]));
					}
					
					
				}

				
			}
			
			
			
		}
		
		
		
}


class Edge implements Comparable<Edge>{  //vertex 정보들
	int vt;
	int dt;
	
	Edge(int vertex, int distance){
		vt = vertex;
		dt = distance;
	}
	
	public int compareTo(Edge edge) {
		return this.dt-edge.dt;
		
	}
}

aeternussm 2년 전 0

83, 85번줄에 +e.vt 가 아니라 +e.dt 같아요

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

문제

문제

출처

ICPC

[자바] 최단경로가 1개만 다르게 나와요...

billy1770 2년 전 0

aeternussm 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말