글 읽기 - C++ dfs로 풀려는데 솔루션을 찾아봐도 어디가 틀렸는지 모르겠습니다.

2147483647 3년 전 0

예제는 제대로 나오는데

예제 말고 다른 반례가 있는지 궁금합니다.

#include <iostream>
#include <vector>

using namespace std;

vector<vector<pair<int,int>>>nodes;
bool dp1toggle[100001]{ 0 };
bool dp2toggle[100001]{ 0 };

pair<int, long long int>deepest = pair<int, long long int>{ 0, 0 };
pair<int, long long int>deepest2 = pair<int, long long int>{ 0, 0 };

void dp1(int idx, long long int depth) {
	if (dp1toggle[idx])return;
	dp1toggle[idx] = 1;
	for (auto x : nodes[idx]) {
		dp1(x.first, depth+x.second);
	}
	if (depth > deepest.second)deepest = pair<int, long long int>{ idx, depth };
}

void dp2(int idx, long long int depth) {
	if (dp2toggle[idx])return;
	dp2toggle[idx] = 1;
	for (auto x : nodes[idx]) {
		dp2(x.first, depth + x.second);
	}
	if (depth > deepest2.second)deepest2 = pair<int, long long int>{ idx, depth };
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int t;
	cin >> t;
	for (int i = 0; i <= t; i++) {
		nodes.push_back(vector<pair<int,int>>{});
	}
	for (int i = 1; i <= t; i++) {
		int x, y;
		cin >> x;
		while (true) {
			cin >> x;
			if (x == -1)break;
			cin >> y;
			nodes[i].push_back(pair<int, int>{x, y});
		}
	}
	//1회차 dfs로 가장 먼 정점을 찾아낸다.
	dp1(1, 0);
	//2회차 dfs로 1회차 dfs에서 얻은 정점에서 가장 먼 정점까리의 거리를 구한다.
	dp2(deepest.first, 0);
	cout << deepest2.second;
}

shg9411 3년 전 2

정점 순으로 입력되지도 않습니다.

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

문제

문제

출처

ICPC

C++ dfs로 풀려는데 솔루션을 찾아봐도 어디가 틀렸는지 모르겠습니다.

2147483647 3년 전 0

shg9411 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말