글 읽기 - 다익스트라 java 반례 있을까요?

jiae031 3년 전 0

게시판에 나오는 반례는 다 맞는듯 한데,

컴파일 초반에 오류나는 걸로 보입니다.

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

//5
//8
//1 2 2
//1 3 3
//1 4 1
//1 5 10
//2 4 2
//3 4 1
//3 5 1
//4 5 3
//1 5

//2
//2
//1 2 10
//1 2 20
//1 2
public class Main {
	
	private static final int MAX = Integer.MAX_VALUE;
	private static ArrayList<ArrayList<Node>> graph;
	private static PriorityQueue<Node> pq;
	private static int shortestPath[];
	private static int start;
	
	//N개의 도시 //M개의 버스
	//마지막 라인에 구하고자 하는 구간
	static class Node implements Comparable<Node>{
		
		int index;
		int weight;
		
		Node(int index, int weight){
			this.index = index;
			this.weight = weight;
		}
		@Override
		public int compareTo(Node o) {
			return this.weight - o.weight;
		}
		
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken()); //도시 수 
		
		st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken()); // 버스대수 
		start = 1;
		
		shortestPath = new int[N+1];
		Arrays.fill(shortestPath, MAX);
		shortestPath[start] = 0;
		
		pq = new PriorityQueue<>();
		graph = new ArrayList<ArrayList<Node>>();
		
		for(int i = 0; i < N + 1; i++) {
			graph.add(new ArrayList<Node>());
		}
		for(int i = 0; i < M ; i++) {
			String st1[] = br.readLine().split(" "); 
			graph.get(Integer.parseInt(st1[0])).add(new Node(Integer.parseInt(st1[1]), Integer.parseInt(st1[2])));
		}
		String ans[] = br.readLine().split(" ");
		int start_a = Integer.parseInt(ans[0]);
		int end_A = Integer.parseInt(ans[1]);
		dijkstra();
		System.out.println(shortestPath[end_A]);
	}
	static void	 dijkstra() {
		pq.offer(new Node(start, 0));
		while(!pq.isEmpty()) {
			Node now = pq.poll();
			
			for(int i = 0; i < graph.get(now.index).size() ; i++) {
				int startV = now.index;
				int endV = graph.get(startV).get(i).index;
				int weight = graph.get(startV).get(i).weight;
				
				if(shortestPath[endV] > shortestPath[startV] + weight) {
					shortestPath[endV] = shortestPath[startV] + weight;
					pq.offer(new Node(endV, shortestPath[startV] + weight));
				}
			}
			
		}
	}

}

djm03178 3년 전 0

시작점이 입력으로 주어졌는데, start_a에 저장만 했을 뿐 실제로는 무조건 1번 정점을 시작점으로 처리하고 있습니다.

jiae031 3년 전 0

정말감사합니다!!

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

문제

문제

출처

ICPC

다익스트라 java 반례 있을까요?

jiae031 3년 전 0

djm03178 3년 전 0

jiae031 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말