글 읽기 - 1504 특정한 최단경로 문제 반례가 뭐가 있을까요?

quki 6년 전 0

68%에서 자꾸만 틀렸다고 하는데 반례를 못찾겠습니다. ㅠㅠ

1-v1-v2-N

1-v2-v1-N

의 경우 중에 최솟값을 출력하는데,

SPFA 로 큐를 만들어서 구현해보았습니다.

Relaxation 시에 큐에 넣는 방식(현재 큐에 들어있지 않은 경우에만)으로 구현했습니다.

웬만한 테스트케이스를 만들어봐도 도저히 왜 틀린지 모르겠습니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static HashMap<Integer, ArrayList<Edge>> graph;
	static int N, M;
	static final int INF = 1000000000;

	static class Edge {
		int v;
		int c;

		Edge(int v, int c) {
			this.v = v;
			this.c = c;
		}
	}

	static int SPFA(int start, int end) {

		int d[] = new int[N + 1];
		boolean isInQueue[] = new boolean[N + 1];

		Arrays.fill(d, INF);
		d[start] = 0;

		Queue<Integer> q = new LinkedList<>();
		q.add(start);
		isInQueue[start] = true; // 현재 큐에 들어가 있는가? 
		while (!q.isEmpty()) {

			int u = q.poll();
			isInQueue[u] = false;

			for (Edge e : graph.get(u)) {
				int v = e.v;
				int c = e.c;

				if (d[v] > d[u] + c) {
					d[v] = d[u] + c;
					if (!isInQueue[v]) {
						q.add(v);
						isInQueue[v] = true;
					}
				}

			}

		}

		return d[end];
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		graph = new HashMap<>();
		for (int i = 1; i <= N; i++) {
			graph.put(i, new ArrayList<Edge>());
		}

		while (M-- > 0) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int c = sc.nextInt();
			graph.get(u).add(new Edge(v, c));
			graph.get(v).add(new Edge(u, c));
		}

		int v1 = sc.nextInt();
		int v2 = sc.nextInt();
		int start = 1;
		int end = N;
		
		// start - v1 - v2 - end
		int p1 = SPFA(start, v1);
		int p2 = SPFA(v1, v2);
		int p3 = SPFA(v2, end);
		int ans1 = p1 + p2 + p3;
		// start - v2 - v1 - end
		int t1 = SPFA(start, v2);
		int t2 = SPFA(v2, v1);
		int t3 = SPFA(v1, end);
		int ans2 = t1 + t2 + t3;
		
		int ans = Math.min(ans1, ans2);
		
		if(ans >= INF){
			System.out.println(-1);
		}else{
			System.out.println(ans);
		}

	}

}

ntopia 6년 전 2

INF 의 0을 하나만 지우면 맞을 것 같네요

왜 그런지는 스스로 생각해보시면 좋을 것 같아요..!

quki 6년 전 0

헉 감사합니다 !

INF를 너무 크게 잡아서 INF를 3번 이상 합치는 경우에 문제가 생기겠네요 ㅠㅠ

빠른 답변 정말 감사드려요!

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

문제

문제

출처

ICPC

1504 특정한 최단경로 문제 반례가 뭐가 있을까요?

quki 6년 전 0

ntopia 6년 전 2

quki 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말