글 읽기 - 11779번 소스 질문입니다.

qkrqudwn12 8년 전 0

테스트 케이스도 맞고 코드도 맞는것같은데 무엇이 틀린지 모르겠네요 ㅠㅠ

import java.util.Scanner;
import java.util.Stack;

public class Main {
	static final int inf = 987654321;

	public static boolean check(boolean bool[], int n) {
		boolean bool2 = false;
		for (int i = 1; i <= n; i++) {
			if (bool[i] == false)
				bool2 = true;
		}
		return bool2;
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();
		int array[][] = new int[n + 1][n + 1];
		for (int i = 0; i < n + 1; i++) {
			for (int j = 0; j < n + 1; j++) {
				array[i][j] = -1;
			}
		}
		while (m-- > 0) {
			int start = scan.nextInt();
			int end = scan.nextInt();
			int cost = scan.nextInt();
			array[start][end] = cost;
		}
		int start = scan.nextInt();
		int end = scan.nextInt();
		int d[] = new int[n + 1];
		boolean bool[] = new boolean[n + 1];
		bool[0] = true;
		for (int i = 1; i <= n; i++) {
			d[i] = inf;
		}
		d[start] = 0;
		int parent[] = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			parent[i] = i;
		}
		parent[start] = -1;
		
		while (check(bool, n)) {

			int index = -1;
			int max = inf + 1;
			for (int i = 1; i <= n; i++) {
				if (max > d[i] && !bool[i]) {
					index = i;
					max = d[i];
				}
			}
			bool[index] = true;

			for (int i = 1; i <= n; i++) {
				if (array[index][i] >= 0 && d[i] > d[index] + array[index][i]) {
					d[i] = d[index] + array[index][i];
					parent[i] = index;
				}
			}
		}
		System.out.println(d[end]);
		Stack<Integer>s=new Stack<Integer>();
		int x=end;
		while(x!=-1){
			s.push(x);
			x=parent[x];
		}
		System.out.println(s.size());
		while(!s.isEmpty()){
			System.out.print(s.pop()+" ");
		}

	}
}

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

문제

문제

출처

ICPC

11779번 소스 질문입니다.

qkrqudwn12 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말