글 읽기 - 답이 틀렸다고 나오는데 어디서 틀린걸까요

uuyzpil 3년 전 0

각 s ,g ,h 에서 다익스트라 한번 돌리고

목적지 후보 쭉 돌면서 아래 조건으로 출력했는데 테스트케이스는 맞는데 어디서 틀린지를 모르겄네요 ㅠㅠ

후보 리스트 오름차순

if (s[후보지] == s[g] + g[h] + h[후보지] ) 후보 출력

else if (s[후보지] == s[h] + h[g] + h[후보지]) 후보 출력

#include <iostream>
#include<vector>
#include<queue>
#include<limits.h>
#include <algorithm>

using namespace std;

struct Edge
{
	int v;
	long long e;
	bool operator<(const Edge &a)const
	{
		return e > a.e;
	}
};

int T, n, m, t, s, g, h;
long long scost[2001], gcost[2001], hcost[2001];
vector<Edge> v[2001];
vector<int> candidate;

void dik(int start)
{
	priority_queue<Edge> q;
	q.push({start,0});
	if (start == s)
	{
		scost[start] = 0;

		while (!q.empty())
		{
			Edge cur = q.top();
			q.pop();
			for (int i = 0; i < v[cur.v].size(); i++)
			{
				Edge next = v[cur.v][i];
				if (scost[next.v] > scost[cur.v] + next.e) {
					q.push({next.v , scost[cur.v] + next.e });
					scost[next.v] = scost[cur.v] + next.e;
				}
			}
		}
	}
	else if (start == g)
	{
		gcost[start] = 0;
		while (!q.empty())
		{
			Edge cur = q.top();
			q.pop();

			for (int i = 0; i < v[cur.v].size(); i++)
			{
				Edge next = v[cur.v][i];
				if (gcost[next.v] > gcost[cur.v] + next.e) {
					q.push({ next.v , gcost[cur.v] + next.e });
					gcost[next.v] = gcost[cur.v] + next.e;
				}
			}
		}
	}
	else if (start == h)
	{
		hcost[start] = 0;
		while (!q.empty())
		{
			Edge cur = q.top();
			q.pop();

			for (int i = 0; i < v[cur.v].size(); i++)
			{
				Edge next = v[cur.v][i];
				if (hcost[next.v] > hcost[cur.v] + next.e) {
					q.push({ next.v , hcost[cur.v] + next.e });
					hcost[next.v] = hcost[cur.v] + next.e;
				}
			}
		}
	}

}

int main(void)
{
	freopen("input.txt", "r", stdin);

	scanf("%d", &T);

	for (int z = 0; z < T; z++)
	{
		candidate.clear();
		for (int i = 0; i < 2001; i++)
		{
			scost[i] = gcost[i] = hcost[i] = LLONG_MAX;
			v[i].clear();
		}

		scanf("%d %d %d", &n ,&m,&t);
		scanf("%d %d %d", &s, &g, &h);

		for (int i = 0; i < m; i++)
		{
			int a, b;
			long long c;
			scanf("%d %d %lld", &a, &b, &c);
			v[a].push_back({b,c});
			v[b].push_back({a,c});
		}
		dik(s);
		dik(g);
		dik(h);
		for (int i = 0; i < t; i++)
		{
			int temp;
			scanf("%d", &temp);
			candidate.push_back(temp);
		}

		sort(candidate.begin(), candidate.end());
		for (int i = 0; i < t; i++)
		{
			int desti = candidate[i];
			if (scost[desti] == scost[g] + gcost[h] + hcost[desti]) printf("%d ", desti);
			else if (scost[desti] == scost[h] + hcost[g] + gcost[desti]) printf("%d ", desti);
		}
		printf("\n");

	}
}

myeongbo123 3년 전 0

s와 g가 같을 수도 있습니다. 그런 경우에도 scost와 gcost에 최단 거리가 정상적으로 저장이 되어야 하는데 위 코드에 의하면 g와 s가 같을 경우 모두 28번 줄의 조건에 걸리게 되어 scost에만 최단 거리가 정상적으로 저장이 되고 gcost는 전혀 갱신되지 않습니다. 그 부분만 수정하면 될 듯 합니다.

myeongbo123 3년 전 0

개인적인 의견으로는 dik 함수에 long long 형 배열도 매개변수로 추가해 scost, gcost, hcost 한꺼번에 처리하는 게 어떨까 합니다.

uuyzpil 3년 전 0

답변 감사합니다. g + s 거리를 찾아서 더해주면 되는거였는데 그걸 캐치를 못해서 틀렸었네요

친절한 답변 감사드립니다.

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

문제

문제

출처

ICPC

답이 틀렸다고 나오는데 어디서 틀린걸까요

uuyzpil 3년 전 0

myeongbo123 3년 전 0

myeongbo123 3년 전 0

uuyzpil 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말