[BOJ/Gold 4] 백준 33531 Doner Time!(C++)

문제 링크

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

 

문제

Every student knows the practice: after having had one too many drinks in the \PUB, you will go to the Doner Shop to treat yourself with some comfort food.

But experience tells you that you and your friends will not recall the way to the Doner Shop when you are drunk. Besides there are a lot of Doner Shops in the city. Therefore you decide to write a program that will tell you how far away the nearest Doner store is from your current location. And tells you with Doner store is closest.

You may assume you can reach at least one Doner Shop from your current location. You always start at the crossing numbered 1.

 

입력

A line with two integers: N,1 < N ≤ 10,000, the number of crossings in the city, and S,1 < S ≤ 100,000, the number of streets in the city.

 S lines with three space seperated integers, a, b, l, 1 ≤ a, b ≤ N, 1 ≤ l ≤ 1,000. Which indicate that a street with length l connects crossing a with crossing b. All streets are bi-directional.

An integer m,1 ≤ m ≤ 1,000, the number of Doner Shops in the city.

 M lines with one integer c,1 ≤ c ≤ N which indicates that on crossing c you can find a Doner shop.

 

출력

One line with two space separated integers:

 C The number of the crossing at which you can find the closest Doner Shop. If multiple doner stores are equally far away from you, give the one that has the lowest number.

 L The length of the shortest route to the closest Doner Shop.

 

예제 입력 1

6 6
1 2 5
1 5 1
5 3 2
2 3 1
2 4 1
3 6 3
2
4
6

예제 출력 1

4 5

예제 입력 2

11 13
1 2 5
2 3 30
2 4 16
4 3 17
2 5 6
5 6 7
6 10 8
10 9 12
8 9 11
8 11 14
7 8 10
1 7 9
5 8 13
3
11
10
3

예제 출력 2

10 26

 

알고리즘 분류

• 최단 거리 알고리즘

 

풀이

 

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 10001
#define LL long long
#define INF 1e12
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, S, A, B, L, M, C;
vector<pair<int, int> > Edges[MAX];
priority_queue<pair<LL, int> > PQ;
LL Dist[MAX];
bool isDoner[MAX];
LL AnswerA, AnswerB = INF;

void init() {
	for (int i = 0; i < MAX; i++) {
		Dist[i] = INF;
	}
}

void input() {
	cin >> N >> S;
	for (int i = 0; i < S; i++) {
		cin >> A >> B >> L;
		Edges[A].push_back(make_pair(B, L));
		Edges[B].push_back(make_pair(A, L));
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> C;
		isDoner[C] = true;
	}
}

void dijkstra() {
	Dist[1] = 0;
	PQ.push(make_pair(0, 1));

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

		for (int i = 0; i < (int)Edges[NowX].size(); i++) {
			int NextX = Edges[NowX][i].first;
			LL NextD = Edges[NowX][i].second;
			if (Dist[NextX] > Dist[NowX] + NextD) {
				Dist[NextX] = Dist[NowX] + NextD;
				PQ.push(make_pair(-Dist[NextX], NextX));
			}
		}
	};
}

void settings() {
	dijkstra();
	for (int i = 1; i <= N; i++) {
		if (!isDoner[i]) continue;
		if (AnswerB > Dist[i]) {
			AnswerA = i;
			AnswerB = Dist[i];
		}
	}
}

void printAnswer() {
	cout << AnswerA << " " << AnswerB << "\n";
}

int main() {
	FASTIO

	init();
	input();
	settings();
	printAnswer();

	return 0;
}