SWEA 1251 : 하나로[D4] (c++)_(priority_queue)

* 문제 링크 :

https://swexpertacademy.com/main/main.do -> 로그인 -> 문제은행 -> '1251' or '하나로' 검색

 

** 문제 풀이 방법

Goal) N개의 섬 최소 길이로 모두 연결   - 1<=N<=1,000   - 0<= X,Y<= 1,000,000   - 0<= E <= 1 <순서> 1) 섬 좌표(X, Y) 입력 받기 2) i 도시에서 j 도시 거리 행렬 만들어 놓기(매번 연산 x) 3) priority_queue를 사용 속도 향상

 

*** 코드

#include <stdio.h>
#include <queue>
#include <time.h>

#define MAX_NUM 1001
#define INF 987654312987654321LL
#define SQUARE(X) (X)*(X)

typedef long long ll;

struct map {
	int x, y;
};

class edge {
public:
	int end;
	ll distance;

	edge(int _end, ll _distance) {
		this->end = _end;
		this->distance = _distance;
	}

	bool operator < (const edge& others) const {
		return this->distance > others.distance;
	}
};

using namespace std;

int N;
map coord[MAX_NUM];
int visited[MAX_NUM];
ll dist_matrix[MAX_NUM][MAX_NUM];
priority_queue<edge>pq;
ll dist[MAX_NUM];
double E;
ll result;

void init() {
	scanf("%d ", &N);

	for (int i = 1; i <= N; i++) {
		dist[i] = INF;
		visited[i] = 0;	// 방문하기전 0, 방문 후 1;
	}

	int x, y;
	for (int i = 1; i <= N; i++) {
		scanf("%d ", &x);
		coord[i].x = x;
	}
	for (int i = 1; i <= N; i++) {
		scanf("%d ", &y);
		coord[i].y = y;
	}

	scanf("%lf ", &E);
}

void Dist_cal() {
	for (int i = 1; i < N; i++) {
		for (int j = i + 1; j <= N; j++) {
			ll gap_x = coord[i].x - coord[j].x;
			ll gap_y = coord[i].y - coord[j].y;
			ll x_dist = SQUARE(gap_x);
			ll y_dist = SQUARE(gap_y);
			dist_matrix[i][j] = dist_matrix[j][i] = x_dist + y_dist;
		}
	}
}

void MST() {

	dist[1] = 0;
	pq.emplace(edge(1, 0));

	int cur = 0;
	while (!pq.empty()) {
		cur = pq.top().end;
		pq.pop();
		if (visited[cur]) continue;
		visited[cur] = 1;

		for (int i = 1; i <= N; i++) {
			if (!visited[i] && (dist[i] > dist_matrix[cur][i])) {
				dist[i] = dist_matrix[cur][i];
				pq.emplace(edge(i, dist[i]));
			}
		}
	}

	result = 0;
	for (int i = 1; i <= N; i++) {
		result += dist[i];
	}
}

int main(){

	clock_t start = clock(); // 시작시각 체크

	freopen("input.txt", "r", stdin);
	int TC;
	scanf("%d", &TC);

	for (int tc = 1; tc <= TC; tc++) {
		init();
		Dist_cal();
		MST();

		printf("#%d %.0f\n", tc, result*E);
	}

	printf("Time : %dms", clock() - start); // 소요시간 확인용

	return 0;
}

 

**** 주의할 점

• 자료형 주의: double, int, long long

 

 

 

 

 

<Reference>

-  https://swexpertacademy.com/main/main.do