글 읽기 - [JAVA] 어디가 틀린지 봐주세요ㅠ

jiys5164 6년 전 0

우선순위 큐가 아닌 그냥 큐를 이용해서 코드를 짜봤는데

1->a->b ->n / 1->b->a->n 중에 더 작은 것을 출력하고

1->a / 1->b / 1->n 중 하나라도 연결이 안되어있으면 -1을 출력하게 해놨는데 10% 에서 정답이 틀리다고 나오네요

아직 많이 초보라서 코드가 지저분해 보일수 있습니다 ㅠㅠ

package BOJ;

import java.util.Scanner;

public class Main {
	
	public static final int INF = 100000000;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt(); int e = scanner.nextInt();
		int [][]myArr = new int[n+1][n+1];
		
		for(int i = 1; i <= e; i++) {
			int a = scanner.nextInt(); int b = scanner.nextInt();
			myArr[a][b] = myArr[b][a] = scanner.nextInt();
		}
		int course1 = scanner.nextInt(); int course2 = scanner.nextInt();
		
		long dist1 = dijkstra(myArr, n, 1, course1) + dijkstra(myArr, n, course1, course2) + dijkstra(myArr, n, course2, n);
		long dist2 = dijkstra(myArr, n, 1, course2) + dijkstra(myArr, n, course2, course1) + dijkstra(myArr, n, course1, n);
		
		if(dijkstra(myArr, n, 1, n) == INF || dijkstra(myArr, n, 1, course1) == INF || dijkstra(myArr, n, 1, course2) == INF) System.out.println(-1);
		else if(dist1 > dist2) System.out.println(dist2);
		else System.out.println(dist1);
		
		scanner.close();
	}
	
	public static long dijkstra(int [][]myArr, int n, int start, int end) {
		Queue queue = new Queue();
		long []distance = new long[n+1];
		boolean []isVisit = new boolean[n+1];
		
		for(int i = 0; i < n+1; i++) {
			distance[i] = INF;
			isVisit[i] = false;
		}
		
		distance[start] = 0; isVisit[start] = true;
		queue.enQueue(start);
		
		while(!queue.isEmpty()) {
			int curPos = queue.queueArr[queue.front];
			long curDis = distance[curPos];
			queue.deQueue();
			for(int i = 1; i <= n; i++) {
				if(!isVisit[i] && myArr[curPos][i] != 0) {
					isVisit[i] = true;
					queue.enQueue(i);
					distance[i] = curDis + myArr[curPos][i];
				}
			}
		}
		
		return distance[end];
		
	}
	
	public static class Queue {
		public int []queueArr;
		public int front, rear;
		
		Queue() {
			queueArr = new int[801];
			front = 0; rear = 0;
		}
		
		public boolean isEmpty() {
			if(front == rear) return true;
			else return false;
		}
		
		public void enQueue(int data) {
			if(rear == 801) System.out.println("Queue Full");
			else {
				queueArr[rear] = data;
				rear++;
			}
		}
		
		public void deQueue() {
			if(isEmpty()) System.out.println("Queue empty");
			else {
				front++;
			}
		}
	}
}

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

문제

문제

출처

ICPC

[JAVA] 어디가 틀린지 봐주세요ㅠ

jiys5164 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말