글 읽기 - 최소 스패닝 트리 문제에선 맞췄는데 왜 여기서 틀렸는지 모르겠습니다.

dnjsdudals32 6년 전 0

최소 스패닝 트리 문제에선 맞췄는데 왜 여기서 틀렸는지 모르겠습니다.

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

using namespace std;

class Edge {
public:
	int v1, v2, dis;

	Edge(int v1, int v2, int dis) {
		this->v1 = v1;
		this->v2 = v2;
		this->dis = dis;
	}

	const bool operator>(const Edge& other) const {
		return dis > other.dis;
	}
};

int n, m;
vector<bool> isVisited;
vector<vector<Edge>> edge;
priority_queue<Edge, vector<Edge>, greater<Edge>> que;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;
	edge.resize(n + 1);
	for (int i = 0; i < m; i++) {
		int v1, v2, dis;cin >> v1 >> v2 >> dis;

		edge[v1].push_back(Edge(v1, v2, dis));
		edge[v2].push_back(Edge(v2, v1, dis));
	}
	
	isVisited.assign(n + 1, false);

	isVisited[1] = true;
	for (int i = 0; i < edge[1].size(); i++) {
		que.push(edge[1][i]);
	}

	int cost = 0;
	int maxDis = 0;

	while (!que.empty()) {
		const Edge top = que.top();
		que.pop();

		if (!isVisited[top.v2]) {
			cost += top.dis;
			maxDis = top.dis;

			for (int i = 0; i < edge[top.v2].size(); i++) {
				que.push(edge[top.v2][i]);
			}

			isVisited[top.v2] = true;
		}
	}

	cout << cost - maxDis << "\n";
}

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

문제

문제

출처

ICPC

최소 스패닝 트리 문제에선 맞췄는데 왜 여기서 틀렸는지 모르겠습니다.

dnjsdudals32 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말