글 읽기 - c++ 다익스트라 , 뭐가 틀린건지 예외케이스가 뭐인지 모르겠습니다

jsi6452 2년 전 0

예제는 맞는데 어디서 틀린건지 도저히 모르겠습니다.

g->h를 거쳐 목적지로 가는 최단거리 ,h->g를 거쳐 목적지로 가는 최단거리가

s->목적지로 가는 최단거리와 같다면, 해당 후보군을 출력하는 형태로 코드를 짰는데,

왜 안되는지 모르겠네요,

s->목적지 == s->g->h->목적지 || s->목적지 == s->h->g->목적지

면 후보군을 출력하는건데

예외 케이스가 뭘까요 뭘 실수한걸까요 미치겠네요

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<limits.h>
#include<cstring>
#define INF 987654321

using namespace std;

vector<pair<int, int>> arr[100001];
priority_queue<pair<int, int>>pq;
int visit[100001];

int v, e, t, s, g, h, a, b, c;

int sum, sum2;


void intiate()
{
	for (int i = 1; i <= v; i++)
	{
		visit[i] = INF;

	}
}

void dijkstra(int start)
{
	intiate();
	pq.push(make_pair(0, start));
	visit[start] = 0;

	while (!pq.empty())
	{
		int dist = -pq.top().first;
		int now = pq.top().second;
		pq.pop();
		if (dist > visit[now])
		{
			continue;
		}
		for (int i = 0; i < arr[now].size(); i++)
		{
			int cost = dist + arr[now][i].second;
			int next_node = arr[now][i].first;
			if (visit[next_node] > cost)
			{
				visit[next_node] = cost;
				pq.push({ -cost,next_node });
			}
		}
	}
	
}




int main(void)
{
	int test;
	scanf("%d", &test);
	while (test != 0)
	{
		vector<int> list;
		for (int i = 1; i <= e; i++)
		{
			arr[i].clear();
		}

		test--;
		scanf("%d %d %d", &v, &e, &t);
		scanf("%d %d %d", &s, &g, &h);

		for (int i = 1; i <= e; i++)
		{
			scanf("%d %d %d", &a, &b, &c);
			arr[a].push_back(make_pair(b, c));
			arr[b].push_back(make_pair(a, c));
		}

		for (int i = 0; i < t; i++)
		{
			int tmp;
			int stra;
			int GH, HG, SG, SH, Gtmp, Htmp, Stmp, TMP;
			scanf("%d", &tmp);
			dijkstra(s);
			SG = visit[g];
			SH = visit[h];
			Stmp = visit[tmp];

			dijkstra(g);
			GH = visit[h];
			Gtmp = visit[tmp];

			dijkstra(h);
			Htmp = visit[tmp];
			HG = visit[g];

			sum = SG + GH + Htmp;
			sum2 = SH + HG + Gtmp;

			if (sum >= INF || sum2 >= INF || Stmp >= INF)
			{
				break;
			}
			
			if (Stmp == sum)
			{
				list.push_back(tmp);
			}
			else if (Stmp == sum2)
			{
				list.push_back(tmp);
			}


		}
		sort(list.begin(), list.end());

		for (int i = 0; i < list.size(); i++)
		{
			printf("%d ", list[i]);
		}


		list.clear();
		printf("\n");
	}
	
}

tkdgus0782 2년 전 0

이문제를 읽어보면, 단순히 g와 h를 지나간것이아니라, 주어진 g와 h사이를 잇는 도로를 지나간 것입니다.

dijkstra(g);
GH = visit[h];
Gtmp = visit[tmp];

dijkstra(h);
Htmp = visit[tmp];
HG = visit[g];

이부분에서 만약 g와 h를 잇는 직통 도로보다 더 짧은 경로가 존재한다면 오답이 나오지 않을까 싶네요!

간선들을 받으면서 g와 h를 잇는 간선의 길이를 저장해놓았다가 사용하면 될듯합니다.

0archlinux0 2년 전 0

s->g->h->x OR s->h->g->x 경로의 가중치 합 = s->x 을 출력, 두가지의 예외 처리만 해주면 됩니다

Edge case:

1) s == g or s == h

2) x == g or x == h

1의 경우 s에서s로 가는 가중치값을 미리 0으로 초기화,

2의 경우는 g에서 g, h에서 h로 가는 가중치값을 미리 0으로 처리함으로써 해결 할 수 있습니다.

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

문제

문제

출처

ICPC

c++ 다익스트라 , 뭐가 틀린건지 예외케이스가 뭐인지 모르겠습니다

jsi6452 2년 전 0

tkdgus0782 2년 전 0

0archlinux0 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말