글 읽기 - 8%에서 계속 막힙니다.... ㅜㅜ

meringueee 6년 전 0

문제 조건을 제가 잘 이해를 못한건지.....

A나 B까지 최단경로 찾아서 보여주는 부분도 짰고

둘다 도달할 수 없으면 -1 내보내는 것도 했는데,

걱정이었던건 연결 배열 크기가 지나치게 큰 정도 였는데

그게 문제가 되기도 전에 8%에서 틀렸다고 나오네요.....

큐 활용하는 부분이 문제일거다 하고 지레짐작은 하는데 찬찬히 뜯어봐도 잘못된 부분을 모르겠어요 ㅜㅜ

혹시 한 번 봐주시면 정말 감사하겠습니다 ㅜㅜ

import java.util.*; import java.io.*;
public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String inp[]=br.readLine().split(" ");
		int n=Integer.parseInt(inp[0]);
		int m=Integer.parseInt(inp[1]);
		int j=Integer.parseInt(br.readLine());
		int k=Integer.parseInt(br.readLine());
		ArrayList<Integer> As=new ArrayList<Integer>();
		ArrayList<Integer> Bs=new ArrayList<Integer>();
		
		inp=br.readLine().split(" ");
		for(String i:inp) {
			As.add(Integer.parseInt(i));
		}
		inp=br.readLine().split(" ");
		for(String i:inp) {
			Bs.add(Integer.parseInt(i));
		}
		
		
		
		int link[][]= new int[n+1][n+1];
		for(int i=0; i<m; i++) {
			inp=br.readLine().split(" ");
			link[Integer.parseInt(inp[0])][Integer.parseInt(inp[1])]=Integer.parseInt(inp[2]);
			link[Integer.parseInt(inp[1])][Integer.parseInt(inp[0])]=Integer.parseInt(inp[2]);
		}
		
		int distance[]=new int[n+1];
		ArrayList<Integer> queue=new ArrayList<Integer>();
		for(int i=0; i<=n; i++) {
			distance[i]=20000000;
			if(i==j) {
				distance[i]=0;
			}else if(link[j][i]>0) {
				distance[i]=link[j][i];
				queue.add(i);
			}
		}
		//기본값 생성 끝
		int minA=20000000, minB=20000000;
		for(int i=0; i<k; i++) {
			if(i!=m&&distance[As.get(i)]<minA) {minA=distance[As.get(i)];}
			if(i!=m&&distance[Bs.get(i)]<minB) {minB=distance[Bs.get(i)];}
		}
		if(minA<minB) {
			System.out.println("A");
			System.out.println(minA);
		}else if(minB<minA) {
			System.out.println("B");
			System.out.println(minB);
		}else {
			BFS(As, Bs, n, m, link, distance, queue, minA, minB);
		}
	}

	static void BFS(ArrayList<Integer> As, ArrayList<Integer> Bs,
			int n, int m, int link[][], int distance[], ArrayList<Integer> queue,
			int minA, int minB) {
		int tmp, tmpdist;
		while(!queue.isEmpty()) {
			tmp=queue.get(0);
			tmpdist=distance[tmp];
			queue.remove(0);
			
			for(int i=1; i<=n; i++) {
				if(link[tmp][i]>0&&tmpdist+link[tmp][i]<distance[i]) {
					distance[i]=tmpdist+link[tmp][i];
					queue.add(i);
				}
			}
		}
		
		for(int i=0; i<As.size(); i++) {
			if(distance[As.get(i)]<minA) {minA=distance[As.get(i)];}
			if(distance[Bs.get(i)]<minB) {minB=distance[Bs.get(i)];}
		}
		
		if(minA<minB) {
			System.out.println("A");
			System.out.println(minA);
		}else if(minB<minA) {
			System.out.println("B");
			System.out.println(minB);
		}else if(minA<20000000){
			System.out.println("A");
			System.out.println(minA);
		}else {
			System.out.print(-1);
		}
	}
}

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

문제

문제

출처

ICPC

8%에서 계속 막힙니다.... ㅜㅜ

meringueee 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말