글 읽기 - 다익스트라 알고리즘으로 풀어보았습니다 왜 틀릴까요...? ㅠㅠ

kim031504 4년 전 0

반드시 거쳐야 하는 두 개의 정점을 v1, v2라 놓으면

1. start(시작점) -> v1 -> v2 -> end(끝점)

2. start(시작점) -> v2 -> v1 -> end(끝점)

의 두 가지 경우가 나옵니다.

만일 1번의 경우

start -> v1의 다익스트라 적용

v1 -> v2의 다익스트라 적용

v2 -> end의 다익스트라 적용

이렇게 해서 3가지의 값을 더하는 식으로 하고, 2번의 경우도 마찬가지의 프로세스를 따르게 했습니다.

이들 각각의 결과는 case1과 case2라는 변수에 담아 최종적으로 min인 값을 출력하게요!

그리고 갱신이 안 되어 INF(가장 큰 값)이 된 경우에는 -1을 출력하도록 예외처리를 했습니다.

하지만 왜 틀릴까요...?

코드의 자세한 설명은 주석으로 달아놨습니다!

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <queue>

using namespace std;

const int MAX_V = 20000;    // 정점의 최대 개수
const unsigned int INF = 2000000000; // 절대 나올 수 없는 경로값

typedef pair<int, int> P;

int main()
{
	int N, E;

	// 반드시 거쳐야 하는 정점 2개
	int v1, v2;

	unsigned int case1=0, case2=0;

	// 인접 리스트 : (이어진 정점 번호, 거리)를 담는다.
	vector<P> adj[MAX_V];

    // 정점 개수, 간선 개수 입력!
	scanf("%d %d", &N, &E);

	// 인접리스트 정보 입력
	for (int i = 0; i < E; i++)
	{
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);

		adj[u - 1].push_back(P(v - 1, w));
	}

    // 거쳐야 하는 두 개의 정점 입력!
	scanf("%d %d", &v1, &v2);

    // 인덱스를 맞추기 위해 1 감소!
	v1--;
	v2--;

    // 동적으로 최소 거리를 담는 배열
	int dist[MAX_V];

    // 일단 dist를 거의 무한대로 지정한 값 INF로 초기화한다.
	fill(dist, dist + MAX_V, INF);

    // 방문 여부 체크!
	bool visited[MAX_V] = { false, };

	// 최소 힙. first : dist[k], second : K(정점)
	priority_queue<P, vector<P>, greater<P>> PQ;

	/*
		case 1
		1 -> v1 -> v2 -> end
	*/

	// 1) 1 -> v1
	dist[0] = 0;	// 시작점으로의 거리는 0

	PQ.push(P(0, 0));	// 시작점만 PQ에 넣고 시작

	while (!PQ.empty())
	{
		int curr;

		curr = PQ.top().second;
		PQ.pop();

		visited[curr] = true;	// 방문

		for (auto &p : adj[curr])
		{
			int next = p.first, d = p.second;

			if (dist[next] > dist[curr] + d)
			{
				dist[next] = dist[curr] + d;
				PQ.push(P(dist[next], next));
			}
		}
	}

	case1 += dist[v1];
	case2 += dist[v2];

	// 2) v1 ->  v2
	fill(dist, dist + MAX_V, INF);
	fill(visited, visited + MAX_V, false);
	dist[v1] = 0;
	PQ.push(P(0, v1));

	while (!PQ.empty())
	{
		int curr;

		curr = PQ.top().second;
		PQ.pop();

		visited[curr] = true;	// 방문

		for (auto &p : adj[curr])
		{
			int next = p.first, d = p.second;

			if (dist[next] > dist[curr] + d)
			{
				dist[next] = dist[curr] + d;
				PQ.push(P(dist[next], next));
			}
		}
	}

	case1 += dist[v2];

	// 3) v2 -> end
	fill(dist, dist + MAX_V, INF);
	fill(visited, visited + MAX_V, false);
	dist[v2] = 0;
	PQ.push(P(0, v2));

	while (!PQ.empty())
	{
		int curr;

		curr = PQ.top().second;
		PQ.pop();

		visited[curr] = true;	// 방문

		for (auto &p : adj[curr])
		{
			int next = p.first, d = p.second;

			if (dist[next] > dist[curr] + d)
			{
				dist[next] = dist[curr] + d;
				PQ.push(P(dist[next], next));
			}
		}
	}

	case1 += dist[N-1];

	/*
		case 2
		1 -> v2 -> v1 -> end
	*/
	// 1) 1 -> v2
	
	// 이미 위에서 같이 구했음!

	// 2) v2 ->  v1
	fill(dist, dist + MAX_V, INF);
	fill(visited, visited + MAX_V, false);
	dist[v2] = 0;
	PQ.push(P(0, v2));

	while (!PQ.empty())
	{
		int curr;

		curr = PQ.top().second;
		PQ.pop();

		visited[curr] = true;	// 방문

		for (auto &p : adj[curr])
		{
			int next = p.first, d = p.second;

			if (dist[next] > dist[curr] + d)
			{
				dist[next] = dist[curr] + d;
				PQ.push(P(dist[next], next));
			}
		}
	}

	case2 += dist[v1];

	// 3) v1 -> end
	fill(dist, dist + MAX_V, INF);
	fill(visited, visited + MAX_V, false);
	dist[v1] = 0;
	PQ.push(P(0, v1));

	while (!PQ.empty())
	{
		int curr;

		curr = PQ.top().second;
		PQ.pop();

		visited[curr] = true;	// 방문

		for (auto &p : adj[curr])
		{
			int next = p.first, d = p.second;

			if (dist[next] > dist[curr] + d)
			{
				dist[next] = dist[curr] + d;
				PQ.push(P(dist[next], next));
			}
		}
	}

	case2 += dist[N - 1];

	if (min(case1, case2) >= INF)
		printf("%d\n", -1);
	else
		printf("%d\n", min(case1, case2));

	return 0;
}

ha_ram 4년 전 1

4 5
1 2 3
1 3 1
1 4 1
2 3 3
3 4 4
2 3

답 8

위의 반례를 직접 그려보시고 디버깅하시길 권장합니다.

kim031504 4년 전 1

우와! 감사합니다!

두서없이 작성한 코드 분석해주시고 문제점까지 발견해주시다니... ㅠㅠ

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

문제

문제

출처

ICPC

다익스트라 알고리즘으로 풀어보았습니다 왜 틀릴까요...? ㅠㅠ

kim031504 4년 전 0

ha_ram 4년 전 1

kim031504 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말