문제

타임머신

풀이

해당 문제는 벨만 포드 알고리즘을 다루는 문제입니다.
벨만 포드 알고리즘도 이번에 처음 다르게 되는데 가중치가 마이너스를 사용하게 될때 사용하는 알고리즘읍니다

1. 모든 정점을 전부 가보기 위해서는 노선을 도시개수만큼 가보아야 합니다

		distance = new long[n + 1];
        for (int i = 0; i <= n; i++) {
            distance[i] = Integer.MAX_VALUE;
        }

        distance[1] = 0;
        for (int i = 1; i < n; i++) {
            for (City city : arr) {
                if (distance[city.start] == Integer.MAX_VALUE) continue;
                if (distance[city.next] > distance[city.start] + city.time) {
                    distance[city.next] = distance[city.start] + city.time;
                }
            }
        }

2. 만약 음의 사이클이 존재하면 무한히 오래전으로 돌릴수 있기때문에 -1을 출력하고 종료된다

		for (City city : arr) {
            if (distance[city.start] == Integer.MAX_VALUE) continue;
            if (distance[city.next] > distance[city.start] + city.time) {
                System.out.println(-1);
                System.exit(0);
            }
        }

3. 방문이 되지 않은 곳은 -1 또는 기간을 출력한다

		for (int i = 2; i <= n; i++) {
            if (distance[i] == Integer.MAX_VALUE) {
                System.out.println(-1);
            } else {
                System.out.println(distance[i]);
            }
        }

전체 코드

전체 코드