글 읽기 - [C++17] [답이 없는 경우] 제가 어떤 부분을 놓쳤는지 알고싶습니다.

choah76 1년 전 0

다익스트라알고리즘은 동일하나 답이 없는 경우 -1을 출력하는 부분을 다르게 했더니 하나는 맞고 하나는 틀렸습니다.

두 코드가 제가보기에는 동일한 출력을 내놓는 것 같은데 하나는 맞고 하나는 틀렸습니다.

무엇이 다른것인가요?

답이 없는 경우(해당 경로의 거리가 초기값 INF 그대로인 경우) 경로의 거리가 INF 이상이 되기에

1->v1->v2->N 또는 1->v2->v1->N 경로의 거리가 INF 이상이 될 경우(모든 경로의 거리는 0 이상이므로) 답이 없다고 판단, -1을 출력하도록 했습니다.

// 틀린 코드
int ans = min(
		ret1[v1] + ret3[v2] + ret2[v2], // 1 -> v1 -> v2 -> N
		ret1[v2] + ret3[v2] + ret2[v1]	// 1 -> v2 -> v1 -> N
	);
	if (ans >= INF)
		cout << -1;
	else
		cout << ans;


// 맞는 코드
int ans;
	if (ret3[v2] == INF)
		ans = -1;
	else {
		ans = min(
			ret1[v1] + ret3[v2] + ret2[v2], // 1 -> v1 -> v2 -> N
			ret1[v2] + ret3[v2] + ret2[v1]	// 1 -> v2 -> v1 -> N
		);
		if (ans >= INF)
			ans = -1;
	}
	cout << ans;
	

choah76 1년 전 0

전체 코드입니다. 59번째 줄부터 맞는 코드와 틀린 코드의 차이가 본문과 같이 달라집니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define MAX_V 8000
#define INF 987654321

typedef pair<int, int> pii;

int N, E;
int v1, v2;
vector<pii> adj[MAX_V+1];
priority_queue<pii, vector<pii>, greater<pii>> pq;

vector<int> Dijkstra(int st) {
	vector<int> ret(N + 1, INF);
	ret[st] = 0;

	pq.push({ 0, st });

	while (!pq.empty()) {
		int dist = pq.top().first;
		int curr = pq.top().second;
		pq.pop();

		for (unsigned int i = 0; i < adj[curr].size(); i++) {
			int next = adj[curr][i].second;
			int cost = adj[curr][i].first + dist;

			if (cost < ret[next]) {
				ret[next] = cost;
				pq.push({ cost, next });
			}
		}
	}

	return ret;
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	cin >> N >> E;

	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back({ c, b });
		adj[b].push_back({ c, a });
	}
	cin >> v1 >> v2;

	vector<int> ret1 = Dijkstra(1);
	vector<int> ret2 = Dijkstra(N);
	vector<int> ret3 = Dijkstra(v1);

	int ans;
	if (ret3[v2] == INF)
		ans = -1;
	else {
		ans = min(
			ret1[v1] + ret3[v2] + ret2[v2], // 1 -> v1 -> v2 -> N
			ret1[v2] + ret3[v2] + ret2[v1]	// 1 -> v2 -> v1 -> N
		);
		if (ans >= INF)
			ans = -1;
	}
	cout << ans;
	
	return 0;
}

yhj1937 1년 전 4

다음 예시를 생각해보세요.

4 0
2 3

choah76 1년 전 1

간선이 존재하지 않는 그래프에서는 틀린 코드의 경우, INF=987654321을 3번 더하게 되니까 (ret1[v1] + ret3[v2] + ret2[v2])

C++의 INT 범위를 넘어가서 출력이 -1332004333으로 나오게 되고, 따라서 틀리게 되는 것이었군요

감사합니다!

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

문제

문제

출처

ICPC

[C++17] [답이 없는 경우] 제가 어떤 부분을 놓쳤는지 알고싶습니다.

choah76 1년 전 0

choah76 1년 전 0

yhj1937 1년 전 4

choah76 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말