글 읽기 - 64%에서 틀렸습니다. 뜨는데 어떤 예외 상황이 있을까요

ppp7700 6년 전 0

1. 길이 없을때

2. 요금이 0으로도 도착할때

3.비용 초과했을때

4. 주어진 조건이 최소일때
다 쳐리했는데 어떤 케이스일지 감이 안오네요 ㅠ

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int totalFee = sc.nextInt();
		int countOfCity = sc.nextInt() + 1;
		int countOfRoad = sc.nextInt();
		int[][][] graph = new int[countOfCity][countOfCity][2];
		int[][] BottomUpMap = new int[totalFee + 1][countOfCity];

		for (int i = 0; i < countOfCity; i++) {
			for (int j = 0; j < countOfCity; j++) {
				graph[i][j][0] = -1;
			}
		}
		for (int i = 0; i <= totalFee; i++) {
			for (int j = 2; j < countOfCity; j++) {
				BottomUpMap[i][j] = Integer.MAX_VALUE;
			}
		} // forsetting

		for (int i = 0; i < countOfRoad; i++) {
			int startCity = sc.nextInt();
			int endCity = sc.nextInt();
			int lengthOfRoad = sc.nextInt();
			int feeOfRoad = sc.nextInt();

			graph[startCity][endCity][0] = lengthOfRoad;
			graph[startCity][endCity][1] = feeOfRoad;
		}

		Queue<CityAndFee> queue = new LinkedList<CityAndFee>();
		CityAndFee startCity = new CityAndFee(1, 0, 0);
		queue.offer(startCity);

		while (!queue.isEmpty()) {

			CityAndFee nowCity = queue.poll();

			for (int i = 1; i < countOfCity; i++) {

				if (graph[nowCity.cityNumber][i][0] > -1 && nowCity.sumFee + graph[nowCity.cityNumber][i][1] <= totalFee
						&& nowCity.sumLength + graph[nowCity.cityNumber][i][0] <
							 BottomUpMap[nowCity.sumFee + graph[nowCity.cityNumber][i][1]][i]) {

					CityAndFee nextCity = new CityAndFee(i, nowCity.sumLength + graph[nowCity.cityNumber][i][0] ,nowCity.sumFee + graph[nowCity.cityNumber][i][1]);
					BottomUpMap[nextCity.sumFee][i] = BottomUpMap[nowCity.sumFee][nowCity.cityNumber]
							+ graph[nowCity.cityNumber][i][0];

					queue.offer(nextCity);

				} // if

			}

		} // whileBFs

		int result = Integer.MAX_VALUE;
		for (int i = 0; i < totalFee + 1; i++) {
			result = Math.min(BottomUpMap[i][countOfCity - 1], result);
		}

		if (result == Integer.MAX_VALUE) {
			System.out.println(-1);
		} else {
			System.out.println(result);
		}

	}// main

}// class

class CityAndFee {
	int cityNumber;
	int sumLength;
	int sumFee;
	

	public CityAndFee(int cityNumber,  int sumLength, int sumFee) {
		this.cityNumber = cityNumber;
		this.sumLength = sumLength;
		this.sumFee = sumFee;
	}
}// CityAndFee

Juno 6년 전 1

반례입니다.

Input

1 2 100 1

1 2 1 100

Output

100

ppp7700 6년 전 0

아하 동일한 경로에 값이 다른 경우가 있었네요
확실히 돌려보니까 두번째 값으로 들어와서 -1이 출력되네요... 흠
요 부분 생각해 봐야 겠네요

ppp7700 6년 전 1

63%에서 틀리는 예제 동일 경로에 다른값 예제가 맞았어요 2차원 배열로 그래프 만든거 2차원 ArrayList로 만들어서 제출하니까 바로 맞다고 나오네요

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

문제

문제

출처

ICPC

64%에서 틀렸습니다. 뜨는데 어떤 예외 상황이 있을까요

ppp7700 6년 전 0

Juno 6년 전 1

ppp7700 6년 전 0

ppp7700 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말