글 읽기 - 어디가 잘못된건지 잘 모르겠습니다..

jb_0828 3년 전 0

질문 게시판에 있는 반례들을 거의 다 입력해봤는데 잘 나오는 듯합니다.

어디가 잘못된건지 아무리 찾아도 모르겠네요..ㅠㅠ

고수분들 도와주세요ㅠㅠ

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

public class Main{
	static int N,E,v1,v2;
	static int[][] array;
	static ArrayList<Node>[] list;
	static boolean[] visit;
	static int[] dist;
	static int INF = 999999;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		array = new int[N+1][N+1];
		list = new ArrayList[N+1];
		for(int n = 1; n <= N; n++) {
			list[n] = new ArrayList<>();
		}
		for(int e = 0; e < E; e++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			list[a].add(new Node(b, c));
			list[b].add(new Node(a, c));
		}
		
		st = new StringTokenizer(br.readLine());
		v1 = Integer.parseInt(st.nextToken());
		v2 = Integer.parseInt(st.nextToken());
		
		// 1. 출발 -> v1 -> v2 -> 도착
		int dist1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N);
		// 2. 출발 -> v2 -> v1 -> 도착
		int dist2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N);
		
		if(dist1 >= INF && dist2 >= INF) System.out.println("-1");
		else System.out.println(Math.min(dist1, dist2));
	}
	
	static int dijkstra(int start, int end) {
		if(start == end) return 0;
		PriorityQueue<Node> pq = new PriorityQueue<>();
		visit = new boolean[N+1];
		dist = new int[N+1];
		for(int n = 1; n <= N; n++) {
			if(n == start) continue;
			dist[n] = INF;
		}
		
		pq.offer(new Node(start, 0));
		while(!pq.isEmpty()) {
			Node node = pq.poll();
			int current = node.b;
			visit[current] = true;
			for(int n = 0; n < list[current].size(); n++) {
				Node nextNode = list[current].get(n);
				int next = nextNode.b;
				if(!visit[next] && dist[next] > dist[current] + nextNode.c) {
					dist[next] = dist[current] + nextNode.c;
					if(next == end) return dist[next];
					pq.offer(new Node(next, dist[next]));
				}
			}
		}
		
		return INF;
	}

	static class Node implements Comparable<Node>{
		int b,c;
		Node(int b, int c){
			this.b = b;
			this.c = c;
		}
		public int compareTo(Node node) {
			return this.c - node.c;
		}
	}
}

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

문제

문제

출처

ICPC

어디가 잘못된건지 잘 모르겠습니다..

jb_0828 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말