글 읽기 - 시간초과가 납니다. 프림 알고리즘으로 생각하였습니다.

walong 2년 전 0

아래와 같이 프림 알고리즘으로 풀었는데요

쿼리로 주어지는 정점과 간선 정보를 프림 시작시에 초기값으로 넣고 돌리면 그걸 포함한 mst가 그려져셔 테케는 다 맞게 나옵니다.

매 쿼리마다 프림 알고리즘을 돌리게 되서 시간초과가 나는걸까요?

도움 부탁드립니다.

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

struct node {
	int n;
	long long c;
};

struct node1 {
	int s;
	int e;
	int c;
};



int N, M;
vector<node> alist[200001];
int used[200001];
node1 sunsun[200001];

long long dap;


long long operator<(node v, node t) {
	if (t.c < v.c)return 1;
	return 0;
}

long long prim(int a, int b, int c) {
	for (int i = 0; i <= N; i++) {
		used[i] = 0;
	}
	dap = c;

	priority_queue<node> q;
	q.push({ a,0 });
	q.push({ b,0 });

	int cnt = 0;

	while (!q.empty()) {
		node now = q.top();
		q.pop();

		if (used[now.n] == 1)continue;
		used[now.n] = 1;
		cnt++;
		dap = dap + now.c;

		//종료 조건
		if (cnt == N)return dap;

		for (int i = 0; i < alist[now.n].size(); i++) {
			node next = alist[now.n][i];
			if (used[next.n] == 1)continue;
			q.push(next);
		}
	}
	return dap;
}

int main() {
	scanf("%d %d", &N, &M);
	//초기화
	for (int i = 0; i <= N; i++) {
		alist[i].clear();
	}

	//입력 받기
	for (int i = 1; i <= M; i++) {
		int s, e, c;
		scanf("%d %d %d", &s, &e, &c);
		alist[s].push_back({ e,c });
		alist[e].push_back({ s,c });
		sunsun[i] = { s,e,c };
	}

	
	for (int i = 1; i <= M; i++) {
		long long ddap;
		ddap = prim(sunsun[i].s, sunsun[i].e, sunsun[i].c);
		printf("%lld\n", ddap);
	}
	return 0;
}

playsworld16 2년 전 0

매 쿼리마다 프림 알고리즘을 돌리게 되서 시간초과가 납니다.

힌트를 드리자면, mst 그래프를 얻은 후 각 간선마다

1. 간선이 mst 그래프에 있으면 mst 값을 출력

2. 간선이 mst 그래프에 없으면 ...?

2번에 대해 생각해보시면 좋을 것 같습니다.

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

문제

문제

출처

ICPC

시간초과가 납니다. 프림 알고리즘으로 생각하였습니다.

walong 2년 전 0

playsworld16 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말