[BOJ 3075 // C++] Astromeeting

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 3075번 문제인 Astromeeting이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/3075 

3075번: Astromeeting

문제에 따르면 은하 A에서 B까지 이동하는 데에 드는 최소비용은 두 은하 사이의 최단거리의 제곱과 같다.

두 은하 사이의 최단거리는 dijkstra 알고리즘 등을 이용해 간단히 구할 수 있으므로, dijkstra를 n번 돌려 각 사람들로부터 각 은하에 도달하는 비용들을 구하고 이들을 누적해 각 테스트케이스의 답을 구하자. n이 클 경우 floyd-warshall이 더 효율적일 수 있으나 주어지는 입력의 크기가 매우 작으므로 무엇을 사용해도 상관없을 것이다.

 

n명의 사람들이 항상 만날 수 있는 입력만 주어지지만, n명의 사람들이 방문할 수 없는 은하가 입력에 존재할 수는 있다. 해당 은하를 답의 후보로 생각하지 않도록 구현에 유의하자. 글쓴이는 그런 은하의 경우 거리를 무한대(아래 구현에서는 1,000,000,000,000,000,007)로 취급해주었다.

 

또한 각 은하에 도달하는 비용의 누적값은 32비트 정수 자료형으로 저장하지 못하는 큰 수가 나올 수 있음에 유의하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;

int T, P;
vector<pair<int, int>> G[101];
priority_queue<pair<int, int>> pq;
ll total[101];

void dijkstra(int x) {
	vector<int> dist(P + 1);
	dist[x] = 1;
	pq.push(make_pair(-1, x));

	while (!pq.empty()) {
		int d = -pq.top().first, cur = pq.top().second; pq.pop();
		if (dist[cur] < d) continue;
		for (auto& p : G[cur]) {
			int nxt = p.first, dd = p.second;
			if (!dist[nxt] || d + dd < dist[nxt]) {
				dist[nxt] = d + dd;
				pq.push(make_pair(-(d + dd), nxt));
			}
		}
	}

	for (int i = 1; i <= P; i++) {
		if (dist[i]) total[i] += (dist[i] - 1) * (dist[i] - 1);
		else total[i] = 1000000000000000007LL; 
	}
}

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

	cin >> T;
	while (T--) {
		int N, Q; cin >> N >> P >> Q;
		for (int i = 1; i <= P; i++) G[i].clear(), total[i] = 0;
		vector<int> pp(N);
		for (int i = 0; i < N; i++) cin >> pp[i];
		while (Q--) {
			int x, y, d; cin >> x >> y >> d;
			G[x].emplace_back(make_pair(y, d));
			G[y].emplace_back(make_pair(x, d));
		}

		for (auto& x : pp) dijkstra(x);

		int ans = -1; ll ansd = 1000000000000000006LL;
		for (int i = 1; i <= P; i++) {
			if (total[i] < ansd) ansd = total[i], ans = i;
		}

		cout << ans << ' ' << ansd << '\n';
	}
}