글 읽기 - 어떤 케이스가 틀린걸까요오오

mrpjs21c 7년 전 0

두번째 소스 짜서 도전했는데 계속 WA가 나오네요 ㅋㅋㅋ ㅜㅜ

부모-자식 관계, 자매 관계 다 고려했는데 어디서 문제가 나오는걸까요 ㅎㅎㅎ

로직은 매우 간단합니다 ㅎㅎ. 시작점에서부터 루트까지 올라가면서 차례로 마킹하구요,

목표 점에서도 루트까지 올라가면서 마킹하는데, 이미 마킹이 되있으면 LCA이기 때문에 두 거리를 더합니다.

트리에 예외 케이스가 더 있을까요? ㅇㅅㅇ

특이한 케이스 아시는 분은 공유좀 부탁드립니다 ㅜ

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

int n = 0, m=0;


vector<pair<int, int>> tree;
pair<int, int> nod[40001];
int nod_cnt = 0;
long long dist[40001] = { 0, };
long long dist_a = 0, dist_b = 0;
void foo(int idx, int val)
{
	if (dist[idx] >= 0)
	{
		dist_a = dist[idx];
		dist_b = val;
		return;
	}

	dist[idx] = val;

	if (tree[idx].first > 0)
		foo(tree[idx].first, val + tree[idx].second);
}

int main()
{
	cin >> n;
	for (int i = 0; i <= n; i++)
		tree.push_back(nod[nod_cnt++]);
	for (int i = 0; i < n - 1; i++)
	{
		int a = 0, b = 0, v = 0;
		cin >> a >> b >> v;
		tree[b].first = a;
		tree[b].second = v;
	}
	cin >> m;

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j <= n; j++)
			dist[j] = -1;

		int a = 0, b = 0;
		cin >> a >> b;

		//a와 b사이의 거리 구하기
		foo(a, 0);
		foo(b, 0);

		cout << dist_a + dist_b << endl;

	}

	return 0;
}

etaehyun4 7년 전 1

입력으로 노드 쌍이 주어질 때 무조건 부모, 자식 관계로 들어온다는 보장이 없는 듯 합니다.

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

문제

문제

출처

ICPC

어떤 케이스가 틀린걸까요오오

mrpjs21c 7년 전 0

etaehyun4 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말