글 읽기 - 1504 특정한 최단 경로 왜 틀렸을까요?

wxogus25 7년 전 0

변수 오버플로우도 방지하고 간선 입력받을때 중복된 간선이 있으면 그중 작은 값을 고르도록 해놓고

1 -> x -> y -> n 과 1 -> y -> x -> n 도 구분했는데 왜 안될까요?

(수정)

인접행렬 대신 벡터를 사용하고 우선순위 큐 대신 직접 검사하는 것으로 func 부분을 바꿨더니 통과했습니다....

func 함수 안에있는 if문 아니면 인접행렬과 우선순위 큐 때문인 것 같은데 왜 틀렸는지는 모르겠네요

(통과한 소스 : https://www.acmicpc.net/source/3667231)

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <functional>
#define INF 2100000000

using namespace std;

int n, e;
int metrix[1000][1000];
long long int dis[1000];
priority_queue < pair<long long int, int>, vector<pair<long long int, int> >, greater<pair<long long int, int> > > edge;

void func(int st)
{
	int now, i, j;
	for (i = 1; i <= n; i++)
		dis[i] = INF;
	dis[st] = 0;
	edge.push(make_pair(0, st));
	while(!edge.empty())
	{
		now = edge.top().second;
		edge.pop();
		for (j = 1; j <= n; j++)
		{
			if (metrix[now][j] != 0)
			{
				if (dis[j] == INF)
				{
					dis[j] = dis[now] + metrix[now][j];
					edge.push(make_pair(dis[j], j));
				}
				else
				{
					dis[j] = min(dis[j], dis[now] + metrix[now][j]);
				}
			}
		}
	}
}

int main()
{
	int a, b, c, middel_x, middel_y;

	cin >> n >> e;

	while (e--)
	{
		cin >> a >> b >> c;
		if (a == b) continue;
		if (metrix[a][b] < c && metrix[a][b] != 0) continue;
		metrix[a][b] = metrix[b][a] = c;
	}

	cin >> middel_x >> middel_y;

	long long int x_to_1, x_to_n, y_to_1, y_to_n, x_to_y;

	func(middel_x);
	x_to_1 = dis[1];
	x_to_n = dis[n];
	x_to_y = dis[middel_y];

	func(middel_y);
	y_to_1 = dis[1];
	y_to_n = dis[n];

	long long int dap1 = x_to_1 + x_to_y + y_to_n;
	long long int dap2 = x_to_n + x_to_y + y_to_1;
	if (dap1>=INF && dap2>=INF)
	{
		cout << -1;
	}
	else
	{
		cout << ((dap1 < dap2) ? (dap1) : (dap2));
	}
}

yohan5050 7년 전 2

코드 43번째 줄에서

dis[j] = min(dis[j], dis[now] + metrix[now][j]);

dis[j]가 더 작은 값으로 업데이트 되면 priority queue에 넣어줘야 합니다.

실제로 그 부분만 고쳐서 해보니 맞았습니다.

https://www.acmicpc.net/source/3690513

wxogus25 7년 전 2

아 이미 방문한 정점이라고 해도 값이 변경된다면 그 변경된 값으로 주위를 한번 더 둘러봐야되니까 큐에 추가해 줘야 되네요

아무 생각없이 이미 들른 정점이니까 다시 탐색하지 않도록 한 것 같습니다.

감사합니다! 다음부터는 거의 다짠 코드 다시 짤 일은 없을거같네요 ㅠㅠ

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

문제

문제

출처

ICPC

1504 특정한 최단 경로 왜 틀렸을까요?

wxogus25 7년 전 0

yohan5050 7년 전 2

wxogus25 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말