백준 9694번, 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 풀이

문제

백준 9694번

풀이

0번 정점(한신이)부터 최고의원을 만나기까지 친밀도의 합을 최소화하려면 최단 경로를 구하는 알고리즘을 사용하면 됩니다.

 

0번 정점을 시작 정점으로 잡아두고 다익스트라를 돌려주고, 각 정점을 갱신할 때마다 방문했던 정점들을 업데이트하면 쉽게 풀 수 있습니다.

 

$ T $가 $ 100 $ 미만이고 $ N $이 $ 20 $ 이하이므로 플로이드-워셜(Floyd-Warshall)을 사용하더라도 $ O(TN^3) $에 풀릴 것 같습니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);

	int t;
	cin >> t;
	for (int i = 1; i <= t; i++) {
		int n, m;
		vector<int> dist(21, 1e9), prev(21, -1);
		vector<pair<int, int>> graph[21] = {{},};
		cin >> n >> m;
		priority_queue<pii> pq;

		while (n--) {
			int x, y, z;
			cin >> x >> y >> z;

			graph[x].emplace_back(y, z);
			graph[y].emplace_back(x, z);
		}

		pq.push({0, 0});

		while (!pq.empty()) {
			pii a = pq.top();
			pq.pop();
			int cost = -a.first, u = a.second;

			if (cost > dist[u]) continue;
			for (const auto &next : graph[u]) {
				if (dist[next.first] > next.second + cost) {
					prev[next.first] = u;
					pq.push({-(dist[next.first] = next.second + cost), next.first});
				}
			}
		}

		stack<int> ans;
		for (int k = m - 1; k > 0;) {
			ans.push(k = prev[k]);
		}

		cout << "Case #" << i << ": ";
		if (ans.top()) {
			cout << "-1\n";
		} else {
			while (!ans.empty()) {
				cout << ans.top() << " ";
				ans.pop();
			}
			cout << m - 1 << " \n";
		}
	}
}