[BOJ/Gold 4] 백준 12834 주간 미팅(C++)

문제 링크

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

12834번: 주간 미팅

 

문제

만약 KIST 기사단 2기로 여러분이 선발된다면, 서울 월곡에 있는 KIST와 양재에 있는 씨알푸드에서 팀이 함께 만나 의논하고 함께 작업할 시간을 가지게 된다. 누구나 그 회의 장소에 빨리 가고 싶은 마음은 똑같을 것이다.

각 장소를 노드로 생각하고, 연결된 도로를 간선으로 생각하면 그래프를 구성할 수 있다. KIST 기사단 N명의 집이 있는 노드 번호와 KIST, 씨알푸드의 노드 번호가 주어지고, 한 사람의 거리 di = (집-KIST의 최단 거리) + (집-씨알푸드의 최단 거리)로 정의된다. 단, 도달할 수 없는 경우의 최단 거리는 -1로 정의한다. 예를 들어, 어떤 사람이 KIST로는 갈 수 없고 씨알푸드까지의 최단 거리가 10인 경우 이 사람의 거리 d는 9이고, 다른 사람이 KIST, 씨알푸드로 모두 갈 수 없을 경우 이 사람의 거리 d는 -2이다. 이때 Σdi의 값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 KIST 기사단 팀원의 수 N, 장소의 수 V, 도로의 수 E가 주어진다. (N ≤ 100, V ≤ 1000, E ≤ 10000)

둘째 줄에 KIST의 위치 A와 씨알푸드의 위치 B가 주어진다. (1 ≤ A, B ≤ V)

셋째 줄에 팀원 N명의 집의 위치 Hi가 공백을 사이에 두고 주어진다. (1 ≤ i ≤ N, 1 ≤ Hi ≤ V)

넷째 줄부터 E+3번째 줄까지는 도로의 양 끝 장소 a, b와 길이 l이 주어진다. (1 ≤ a, b ≤ V, 1 ≤ l ≤ 100)

출력

모든 사람의 최단 거리의 합을 출력한다. 단, KIST나 씨알푸드로 갈 수 없는 경우에는 -1로 처리한다.

예제 입력 1

2 5 10
3 5
2 4
3 2 91
1 3 44
5 3 93
1 4 1
4 5 53
4 2 23
5 1 60
2 1 63
3 4 38
5 2 17

예제 출력 1

156

알고리즘 분류

• 최단 거리 알고리즘

풀이

전형적인 다익스트라를 활용할 수 있는 문제였다.

정보를 입력받고, 다익스트라를 총 N번 시행하면서 1부터 N까지 집에서 KIST와 씨알푸드까지의 거리의 합을 구하고, 거리의 합들의 합을 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1001
#define LL long long
#define INF 1e12

using namespace std;
int N, V, E;
vector<pair<int, LL> > Edge[MAX];
int KIST, CRFOOD;
int House[MAX];
LL Cost[MAX];
LL answer = 0;

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

void Input() {
	cin >> N >> V >> E;
	cin >> KIST >> CRFOOD;
	for (int i = 1; i <= N; i++) {
		cin >> House[i];
	}
	for (int i = 0; i < E; i++) {
		int A, B;
		LL L;
		cin >> A >> B >> L;
		Edge[A].push_back(make_pair(B, L));
		Edge[B].push_back(make_pair(A, L));
	}
}

void Dijkstra() {
	for (int i = 1; i <= N; i++) {
		Init();
		priority_queue<pair<LL, int> > PQ;
		Cost[House[i]] = 0;
		PQ.push(make_pair(0, House[i]));

		while (!PQ.empty()) {
			LL CurCost = -PQ.top().first;
			int CurX = PQ.top().second;
			PQ.pop();

			if (Cost[CurX] < CurCost) {
				continue;
			}

			for (int i = 0; i < Edge[CurX].size(); i++) {
				LL nextCost = Edge[CurX][i].second;
				int nextX = Edge[CurX][i].first;
				if (Cost[nextX] > CurCost + nextCost) {
					Cost[nextX] = CurCost + nextCost;
					PQ.push(make_pair(-Cost[nextX], nextX));
				}
			}
		};
		LL KIST_Cost = Cost[KIST];
		LL CRFOOD_Cost = Cost[CRFOOD];
		if (KIST_Cost == INF) {
			KIST_Cost = -1;
		}
		if (CRFOOD_Cost == INF) {
			CRFOOD_Cost = -1;
		}
		answer += (KIST_Cost + CRFOOD_Cost);
	}
}

void Find_Answer() {
	cout << answer << "\n";
}

int main() {
	FASTIO
	Input();
	Dijkstra();
	Find_Answer();

	return 0;
}