글 읽기 - 33%에서 틀리다고 나옵니다

pdc5003 1년 전 0

BFS를 이용해서 풀어보려고 하는데

봤을 때 잘 나오는데 예제나 질문 게시판에 반례도 적용시켜

어디가 잘못 됬는지 잘 모르겠습니다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
typedef long long ll;

int N;
ll totallDist = 0;

vector<vector<ll>> houseInfo;

void BFS()
{
	queue<int> q;
	q.push(1);

	ll lastDist = 0;

	while (q.empty() == false)
	{
		int current = q.front();
		q.pop();

		for (int i = 1; i < houseInfo[current].size(); i++)
		{
			if (houseInfo[current][i] == 0)
				continue;

			lastDist = max(lastDist, houseInfo[current][i]);

			houseInfo[current][i] = 0;
			houseInfo[i][current] = 0;

			q.push(i);

		}

		totallDist += lastDist;
		lastDist = 0;
	}
}


int main()
{
	cin >> N;

	houseInfo.assign(N+1, vector<ll>(N+1,0));

	for (int i = 1; i < N; i++)
	{
		int room1, room2, dist;
		cin >> room1 >> room2 >> dist;
		houseInfo[room1][room2] = dist;
		houseInfo[room2][room1] = dist;
	}

	BFS();

	cout << totallDist;



	return 0;
}

tkdwo7699 1년 전 1

1 2 1

2 3 2

2 4 4

3 5 5

2 6 1

bfs에서 큐에 저장할때 여태 이 경로가 지나간 거리도 함께 저장해야합니다 코드에서 지나오지않은 거리까지 포함합니다.

pdc5003 1년 전 0

감사합니다 덕분에 해결했습니다.

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

문제

문제

출처

ICPC

33%에서 틀리다고 나옵니다

pdc5003 1년 전 0

tkdwo7699 1년 전 1

pdc5003 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말