글 읽기 - 1219번 질문드립니다 예제는 다 맞는데 틀렸다고 뜨네요

shin8469 6년 전 0

예제는 다 맞는데 계속 실패가 떠서 답답하네요

어떤게 잘못됬는지 아시는분 알려주시면 감사하겠습니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

class Road {
	int city;
	int money;

	public Road(int city, int money) {
		super();
		this.city = city;
		this.money = money;
	}

}

public class Main {

	static int n;
	static int start, end;
	static int t;
	static long[] dist;
	static ArrayList<Road>[] city;
	static int[] money;
    static boolean updated;
	static final long max = Long.parseLong("99999999999999");

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		n = scan.nextInt();
		start = scan.nextInt();
		end = scan.nextInt();
		t = scan.nextInt();
		dist = new long[100];
		city = new ArrayList[100];
		money = new int[100];

		for (int i = 0; i < n; i++) {
			city[i] = new ArrayList<Road>();
		}

		for (int i = 0; i < t; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			int c = scan.nextInt();
			city[a].add(new Road(b, -c));

		}
		for (int i = 0; i < n; i++) {
			money[i] = scan.nextInt();
		}

		Arrays.fill(dist, -max);
		dist[start] = money[start];

		for (int k = 0; k < n; k++) {
            updated=false;
			for (int i = 0; i < n; i++) {
				int size = city[i].size();

				for (int j = 0; j < size; j++) {
					int ci = city[i].get(j).city;
					int mo = city[i].get(j).money;
					if (k == 0) {
						city[i].get(j).money += money[ci];
					}
					int mo2 = city[i].get(j).money;

					if (dist[ci] < dist[i] + mo2) {
						dist[ci] = dist[i] + mo2;
                        updated=true;

					}
				}
			
			

			}
            if(!updated) break;

		}

		if (dist[end] == -max)
		{
			System.out.println("gg");
			return;
		}
        if(updated){
            System.out.println("Gee");
            return;
        }    
    

		System.out.println(dist[end]);

	}

}

koosaga 6년 전 0

두번의 iteration으로 사이클 여부를 체크할 수는 없습니다.

힌트 : 벨만 포드 음수 사이클 검출 같은 키워드로 검색해보세요.

shin8469 6년 전 0

검색해서 조건을 수정해도 틀렸다고 뜨네요 ㅠ 예제는 다 되는데.. 제가 잊은 조건이 있는가요?

koosaga 6년 전 2

어떤 조건을 바꾸셨는지 모르겠지만.. 조건의 문제가 아니라 그냥 알고리즘이 틀렸어요

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

문제

문제

출처

ICPC

1219번 질문드립니다 예제는 다 맞는데 틀렸다고 뜨네요

shin8469 6년 전 0

koosaga 6년 전 0

shin8469 6년 전 0

koosaga 6년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말