글 읽기 - 어디서 틀린걸까요..? 최소신장트리-> 다익스트라

wonmo 6년 전 0

음 일단 최소가중치의 엣지 집합을 최소신장트리로 만든 다음에 모든 점에서 다익스트라를 돌린 후 원하는 세점까지의 거리가 가장

적은 점을 찾고 그 점에서 다시 다익스트라 돌린 다음에 prevec이라는 배열에 이전 점을 저장하고 그 점들을 돌아보며 엣지를 출력하도록 했습니다... 어디서 틀린걸까요..?

#include<iostream>
#include<queue>
#include<vector>
#include<functional>
#include<algorithm>
using namespace std;
#define MP make_pair
int cost[1000][1000];
vector<vector<int>> adj;
vector<int> dist,unionFind;
vector<int> prevec;
vector<bool> used;
typedef pair<int, pair<int, int>> Pair;
int n, m, answer = 1e9, p, q, r, startPoint;
queue<pair<int, int>> que;

int find(int a) {
	if (unionFind[a] < 0)return a;
	else return unionFind[a] = find(unionFind[a]);
}

bool unionQuery(int a,int b) {
	int pa = find(a), pb = find(b);
	if (pa == pb)return false;
	else {
		unionFind[pa] = pb;
		return true;
    }
}

void dijkstra(int a) {
	priority_queue<Pair, vector<Pair>, greater<Pair>> pq;
	pq.push(MP(0, MP(a, a)));
	fill(dist.begin(), dist.end(), -1);
	while (!pq.empty()) {
		int flag = pq.top().second.first;
		int pre = pq.top().second.second;
		int weight = pq.top().first;
		pq.pop();
		if (dist[flag] == -1) {
			dist[flag] = weight;
			prevec[flag] = pre;
			for (int i = 0; i < adj[flag].size(); i++) {
				int to = adj[flag][i];
				int pcost = weight + cost[flag][to];
				if (dist[to] == -1) {
					pq.push(MP(pcost, MP(to, flag)));
                }
            }
        }
    }
}

int main() {
	scanf("%d %d", &n, &m);
	adj.resize(n);
	dist.resize(n);
	prevec.resize(n);
	used.resize(n, false);
	unionFind.resize(n, -1);
	priority_queue<Pair, vector<Pair>, greater<Pair>> pq;
	for (int i = 0, x, y, z; i < m; i++) {
		scanf("%d %d %d", &x, &y, &z);
		x--, y--;
		cost[x][y] = cost[y][x] = z;
		pq.push(MP(z, MP(x, y)));
    }
	while (!pq.empty()){
		int weight = pq.top().first;
		int x = pq.top().second.first, y = pq.top().second.second;
		pq.pop();
		if (unionQuery(x, y)) {
			adj[x].push_back(y);
			adj[y].push_back(x);
        }
    }
	scanf("%d %d %d", &p, &q, &r);
	p--, q--, r--;
	for (int i = 0; i < n; i++) {
		dijkstra(i);
		int thisAnswer = dist[p] + dist[q] + dist[r];
		if (answer > thisAnswer) {
			startPoint = i;
			answer = thisAnswer;
        }
    }
	dijkstra(startPoint);
	for (int i = r; i != startPoint && !used[i]; i = prevec[i]) {
		if (prevec[i] == i)break;
		que.push(MP(i + 1, prevec[i] + 1));
		used[i] = true;
    }
	for (int i = p; i != startPoint && !used[i]; i = prevec[i]) {
		if (prevec[i] == i)break;
		que.push(MP(i + 1, prevec[i] + 1));
		used[i] = true;
    }
	for (int i = q; i != startPoint && !used[i]; i = prevec[i]) {
		if (prevec[i] == i)break;
		que.push(MP(i + 1, prevec[i] + 1));
		used[i] = true;
    }
	printf("%d %d\n", answer, que.size());
	while (!que.empty()) {
		printf("%d %d\n", que.front().first, que.front().second);
		que.pop();
    }
	return 0;
}

ehddml3 6년 전 1

1,2,3번 사람이 통화.

답 :

110 2
1 2
1 3

위 코드 출력:

121 3
3 4
4 2
1 2

wonmo 6년 전 1

우왁 너무 감사합니다 ㅠㅠ 최소신장트리로 전처리하면 안되는군요 ㅠ 정말 감사합니다~!! ㅎㅎ

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

문제

문제

출처

ICPC

어디서 틀린걸까요..? 최소신장트리-> 다익스트라

wonmo 6년 전 0

ehddml3 6년 전 1

wonmo 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말