백준 13424 - 비밀 모임(C++)

문제 링크입니다. https://www.acmicpc.net/problem/13424

13424번: 비밀 모임

다익스트라를 이용해 푸는 문제입니다.

1~N번 정점까지 친구들이 있는 곳까지 거리를 각각 구한 뒤, 이를 모두 비교하면 되는 문제입니다.



자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#define INF 2100000000
#define F first
#define S second

using namespace std;

int T, N, M, K;
vector<pair<int ,int>> connect[101]; //x번에서 갈 수 있는 위치와 해당 비용
int Distance[101][101]; //x번에서 y번까지 갈 떄의 최솟값
int Friend[101]; //친구들의 위치를 저장
priority_queue<pair<int, int>, vector<pair<int, int>>> q; //우선순위 큐


void reset_distance(){ // 모든 distance를 초기화한다.
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			Distance[i][j] = INF;
		}
	}
}

void Dijstra(int start){
	Distance[start][start] = 0;
	q.push({-Distance[start][start], start}); // 큐가 오름차순으로 정렬되기에 -값을 넣어준다.
	while(!q.empty()){
		int x = q.top().S;
		int cost = -q.top().F;
		q.pop();
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i].F;
			int n_cost = cost + connect[x][i].S;
			if(Distance[start][xx] > n_cost){ //지금 가려는 위치의 비용이 저장된 값보다 작다면
				Distance[start][xx] = n_cost;
				q.push({-n_cost, xx});
			}
		}
	}
}

void solve(){
	reset_distance();
	for(int i = 1; i <= N; i++) Dijstra(i);
	int ans, maxi = INF;
	for(int i = 1; i <= N; i++){
		int sum = 0;
		for(int j = 1; j <= K; j++){
			sum += Distance[i][Friend[j]]; // 친구들이 있는 곳으로 갈 떄 드는 비용
		}
		if(sum < maxi){
			ans = i;
			maxi = sum;
		}
	}
	cout << ans << "\n";
	for(int i = 1; i <= N; i++) connect[i].clear(); // 저장된 값 초기화
}


int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	for(int i = 1; i <= T; i++){
		cin >> N >> M;
		for(int j = 1; j <= M; j++){
			int x, y, cost;
			cin >> x >> y >> cost;
			connect[x].push_back({y, cost});
			connect[y].push_back({x, cost});
		}
		cin >> K;
		for(int j = 1; j <= K; j++){
			cin >> Friend[j];
		}
		solve();
	}
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.