[BOJ]백준 13424번: 비밀 모임(C++)/Dijkstra

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

13424번: 비밀 모임

또익스트라 구현 코드를 조금 바꿔보았다

이 문제는 입력받은 정점 리스트에 대해 최단거리 합이 가장 작은 정점을 구하는 기본기본 문제였다

 

보편적인 코테 뚫으려면 구현+문자열 위주로 연습해야 되는데 ..... 카카오 코테 준비하려면 다양하게도 풀어야되고 .......... 어떻게 해야될지 정말 ~~~~ 모르겠다 ~~

이제 기본문제 말고 응용문제로 넘어가야지... ㅠㅠ 달빛여우한테 혼났다........

#include <cstdio>
#include <vector>
#include <queue>
#define pii pair<int,int>
#define INF 987654321
using namespace std;

vector<vector<pii>> g;
vector<vector<int>> dist;
int tc,n,m,k;

void dijkstra(int s) {
	dist[s] = vector<int>(n + 1, INF);
	priority_queue<pii,vector<pii>,greater<>> pq;

	dist[s][s] = 0;
	pq.push(make_pair(0, s));

	while (!pq.empty()) {
		int cur = pq.top().second; 
		int cost = pq.top().first; pq.pop();
		if (cost > dist[s][cur])continue;

		for (auto x : g[cur]) 
		if(dist[s][x.second]>cost+x.first){
			dist[s][x.second] = x.first + cost;
			pq.push(make_pair(dist[s][x.second], x.second));
		}
	}
}

int main() {
	scanf("%d", &tc);

	while (tc--) {
		scanf("%d%d", &n, &m);
		g = vector<vector<pii>>(n + 1);
		dist = vector<vector<int>>(n + 1);

		for (int i = 0,a,b,c; i < m; i++) {
			scanf("%d%d%d", &a, &b, &c);
			g[a].push_back(make_pair(c, b));
			g[b].push_back(make_pair(c, a));
		}

		scanf("%d", &k);
		vector<int> f(k);
		for (int i = 0; i < k; i++) {
			scanf("%d", &f[i]);
			dijkstra(f[i]);
		}

		int min = INF,ans;
		for (int i = 1; i <= n; i++) {
			int sum = 0;
			for (int j = 1; j <= n; j++)
				if(!dist[j].empty()) sum += dist[j][i];
			if (sum < min) {
				min = sum;
				ans = i;
			}
		}
		printf("%d\n", ans);
	}

	return 0;
}