글 읽기 - 틀린케이스를 찾을 수가 없네요..ㅠㅠ

filot 7년 전 0

PQ를 이용해서 최단경로를 구하고

2번째를 계속 갱신하도록 했는데

예제는 맞는데..

올리기만 하면 4%에서 틀렸습니다라고 하네요..

몇개 예제로 그려봐도 잘 나온느데.. 어떤 케이스에서 자꾸 문제가 되는건지...

혹시 제가 고려하지 못한게 있는지 조언을 부탁드리겠습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int R;
	static List[] adjList;

    public static void main(String[] args) throws Exception {        
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        StringTokenizer st = new StringTokenizer(reader.readLine());

        N = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        adjList = new List[N + 1];

        for (int i = 1; i <= N; i++)
        	adjList[i] = new ArrayList<Road6197>();

        for (int i = 1; i <= R; i++) {
        	st = new StringTokenizer(reader.readLine());

        	int A = Integer.parseInt(st.nextToken());
        	int B = Integer.parseInt(st.nextToken());
        	int D = Integer.parseInt(st.nextToken());

        	adjList[A].add(new Road6197(A, B, D));
        	adjList[B].add(new Road6197(B, A, D));
        }

        int second = dijkstra(1);

        writer.println(second);

        writer.close();
        reader.close();
    }

    public static int dijkstra(int start) {
    	int[] FIRST_DISTNACE = new int[N + 1];
    	Arrays.fill(FIRST_DISTNACE, Integer.MAX_VALUE);

    	int[] SECOND_DISTANCE = new int[N + 1];
    	Arrays.fill(SECOND_DISTANCE, Integer.MAX_VALUE);

    	boolean[] SET = new boolean[N + 1];
    	Queue<Road6197> QUEUE = new PriorityQueue<Road6197>();

    	FIRST_DISTNACE[start] = 0;
    	QUEUE.offer(new Road6197(start, start, 0));

    	while (!QUEUE.isEmpty()) {
    		Road6197 u = QUEUE.poll();
    		SET[u.B] = true;

    		List<Road6197> list = adjList[u.B];
    		for (Road6197 v : list) {
    			int distance2 = FIRST_DISTNACE[u.B] + v.D;

    			if (!SET[v.B] && FIRST_DISTNACE[v.B] > FIRST_DISTNACE[u.B] + v.D) {
    				distance2 = FIRST_DISTNACE[v.B];
    				FIRST_DISTNACE[v.B] = FIRST_DISTNACE[u.B] + v.D;
    				QUEUE.offer(new Road6197(u.B, v.B, FIRST_DISTNACE[v.B]));
    			}

    			if (SECOND_DISTANCE[v.B] > distance2 && FIRST_DISTNACE[v.B] < distance2) {
    				SECOND_DISTANCE[v.B] = distance2;
    				QUEUE.offer(new Road6197(u.B, v.B, SECOND_DISTANCE[v.B]));
    			}
    		}
    	}

    	return SECOND_DISTANCE[N];
    }
}

class Road6197 implements Comparable<Road6197> {
	int A;
	int B;
	int D;

	public Road6197(int A, int B, int D) {
		this.A = A;
		this.B = B;
		this.D = D;
	}

	@Override
	public int compareTo(Road6197 o) {
		return Integer.compare(this.D, o.D);
	}

	@Override
	public String toString() {
		return "[A=" + A + ", B=" + B + ", D=" + D + "]";
	}
}

jjwdi0 7년 전 1

http://contest.usaco.org/TESTDATA/NOV06_6.htm

이곳에 채점데이터가 있습니다.

filot 7년 전 0

감사합니다.

그런데 테스트케이스를 보니 더 답답하네요.

Test 2의 경우 3 4 2046과 4 3 1395가 있네요.

이 문제 양방향으로 알고 있는데 왜 케이스가 저런게 주어지는지..ㅠㅠ

다른 분들 통과한거 보면 신기하네요.

jjwdi0 7년 전 1

쉽게 말해서, A에서 B로 가는 길이 두 갈래인 겁니다.

만약, 다음과 같은 입력이 있다고 생각합시다.

2 2

1 2 5

2 1 4

여기서 1에서 2로 가는 두 번째 최단경로는 5입니다. (첫 번째는 4겠죠.)

만약, 1에서 2로 가는 간선의 가중치가 15라면, '2 1 4'의 간선을 통해 1 -> 2-> 1 -> 2 의 경로가 두 번째 최단경로겠죠.

감이 잡히시나요? 제가 설명을 잘 못해서..ㅠㅠ

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

문제

문제

출처

ICPC

틀린케이스를 찾을 수가 없네요..ㅠㅠ

filot 7년 전 0

jjwdi0 7년 전 1

filot 7년 전 0

jjwdi0 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말