백준 12834 - 주간 미팅(C++)

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

12834번: 주간 미팅

N번의 다익스트라를 이용하는 문제입니다.

팀원 N명의 집에서 각자 출발할 때, 모든 사람의 최단 거리의 합을 구하는 문제입니다.
최단 거리를 구하는 방법은 X번 사람의 집에서 KIST까지의 거리 + 씨알푸드까지의 거리 입니다.
만약, 거리가 갈 수 없다면 -1로 바꿔서 계산하면 됩니다.

문제를 푸는 방법은 간단하게 N번의 다익스트라를 통해 풀 수 있습니다.
팀원의 집에서 탐색을 시작해서 두 곳까지의 거리를 구한 뒤, 최단 거리를 계산해줍니다.
모든 갑을 더해주면 됩니다.



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

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>
#define INF INT_MAX
#define F first
#define S second

using namespace std;

int N, V, E;
int A, B;
int home[101];
vector<pair<int, int>> connect[1001];
int Distance[1001];
priority_queue<pair<int, int>> q;

void reset_distance(){
	for(int i = 1; i <= V; i++){
		Distance[i] = INF;
	}
}

void Dijstra(int st){
	Distance[st] = 0;
	q.push({-0, st});
	while(!q.empty()){
		int x = q.top().S;
		int cost = -q.top().F;
		q.pop();
		if(Distance[x] < cost) continue;
		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[xx] > n_cost){
				Distance[xx] = n_cost;
				q.push({-Distance[xx], xx});
			}
		}
	}
}

void solve(){
	int sum = 0;
	for(int i = 1; i <= N; i++){
		reset_distance();
		Dijstra(home[i]);
		int dis_1, dis_2;
		if(Distance[A] == INF) dis_1 = -1;
		else dis_1 = Distance[A];
		if(Distance[B] == INF) dis_2 = -1;
		else dis_2 = Distance[B];
		sum += (dis_1 + dis_2);
	}
	cout << sum;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N >> V >> E;
	cin >> A >> B;
	for(int i = 1; i <= N; i++){
		cin >> home[i];
	}
	for(int i = 1; i <= E; i++){
		int x, y, cost;
		cin >> x >> y >> cost;
		connect[x].push_back({y, cost});
		connect[y].push_back({x, cost});
	}
	solve();
	return 0;
}

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