[BOJ/Gold 3] 백준 20160 야쿠르트 아줌마 야쿠르트 주세요(C++)

문제 링크

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

20160번: 야쿠르트 아줌마 야쿠르트 주세요

 

문제

야쿠르트를 외치며 잠에서 깼다. 오늘은 야쿠르트로 하루를 시작하려고 한다.

야쿠르트 아줌마는 10개의 지점을 최단 시간으로 이동하며 들리신다. 각 지점에서 야쿠르트 아줌마보다 같거나 더 일찍 도착한 사람에게 야쿠르트를 팔고 바로 다음 지점으로 출발하신다. 각 지점은 정점 위에 있고 지정된 차례에만 야쿠르트를 판매한다. 야쿠르트를 파는 데 지연되는 시간은 없으며, 오직 이동 시에만 해당 도로의 가중치만큼 시간이 지연된다.

야쿠르트 아줌마는 10개의 지점을 순서대로 방문하며, 10개의 지점 중 첫 번째 지점에서 출발한다. 만약 i번째 지점에서 i+1번째 지점으로 이동 가능한 경로가 없다면 i+2지점으로 이동하신다. i+2로 갈 수 없으면 i+3, i+4...(≤ V)로 이동하신다.

내가 출발하는 시간과 야쿠르트 아줌마가 출발하는 시간은 같다.

내가 출발하는 정점 번호와 야쿠르트 아줌마의 동선을 알려주면 어느 지점으로 가야 야쿠르트를 살 수 있을지 알려줘!!

입력

첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다.

그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤ u, v ≤ V) 사이에 가중치가 w(1 ≤ w ≤ 100,000)인 도로가 존재한다는 뜻이다. 정점 사이에는 여러 개의 간선이 존재할 수도 있음에 유의한다.

E+2번째 줄에는 야쿠르트 아줌마가 야쿠르트를 파는 10개 지점의 정점 번호가 주어진다. E+3번째 줄에는 내가 출발하는 정점 번호가 주어진다.

출력

야쿠르트를 살 수 있는 정점이 여러 개라면 그 중 가장 작은 정점 번호를 출력한다.

야쿠르트를 살 수 없다면 -1을 출력한다.

예제 입력 1

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

예제 출력 1

-1

예제 입력 2

6 5
1 2 1
2 3 10
3 4 100
4 5 1000
5 6 10000
1 2 1 2 1 2 6 5 4 3
6

예제 출력 2

3

예제 입력 3

11 15
6 1 76
4 3 715
7 6 89
11 5 55
7 9 847
8 5 663
3 4 961
2 8 638
1 9 839
3 7 723
6 1 398
3 2 84
8 1 159
10 3 943
6 4 556
1 2 3 4 5 6 7 8 9 10
10

예제 출력 3

5

알고리즘 분류

• 최단 거리 알고리즘

풀이

자신이 어떤 지점까지 가는 데 걸리는 최단 거리를 구하는 다익스트라 1번, 야쿠르트 아줌마다 i번째 지점에서 출발하여 i+1번째 지점으로 도달하는 데 걸리는 최단 거리를 구하는 다익스트라 최대 9번 해서 최대 10번의 다익스트라를 실행한다.

그리고 1번 정점부터 자신이 도달한 시간과 야쿠르트 아줌마가 도달한 시간을 비교해서, 자신이 도달한 시간이 야쿠르트 아줌마가 도달한 시간보다 적거나 같다면 그 정점이 정답이 된다.

코드

#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 10001
#define LL long long
#define INF 1e11

using namespace std;
int V, E, S;
int Yogurt[11];
vector<pair<int, LL> > Edge[MAX];
LL Cost[11][MAX];
LL YCost[11];

void Input() {
	cin >> V >> E;
	for (int i = 1; i <= V; i++) {
		for (int j = 0; j < 11; j++) {
			Cost[j][i] = INF;
		}
	}
	for (int i = 0; i < E; i++) {
		int U, V;
		LL W;
		cin >> U >> V >> W;
		Edge[U].push_back(make_pair(V, W));
		Edge[V].push_back(make_pair(U, W));
	}
	for (int i = 1; i <= 10; i++) {
		cin >> Yogurt[i];
		YCost[i] = INF;
	}
	cin >> S;
}

void Dijkstra(int I, int X) {
	priority_queue<pair<int, int> > PQ;
	Cost[I][X] = 0;
	PQ.push(make_pair(0, X));

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

		if (Cost[I][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[I][nextX] > CurCost + nextCost) {
				Cost[I][nextX] = CurCost + nextCost;
				PQ.push(make_pair(-Cost[I][nextX], nextX));
			}
		}
	};
}

void Settings() {
	int IDX = 1;
	int nextIDX = 2;
	YCost[1] = 0;
	while (1) {
		Dijkstra(nextIDX, Yogurt[IDX]);
		if (Cost[nextIDX][Yogurt[nextIDX]] == INF) {
			nextIDX++;
			if (nextIDX == 11) {
				break;
			}
		}
		else {
			YCost[nextIDX] = Cost[nextIDX][Yogurt[nextIDX]] + YCost[IDX];
			IDX = nextIDX;
			if (IDX == 11) {
				break;
			}
			nextIDX = IDX + 1;
			if (nextIDX == 11) {
				break;
			}
		}
	};
}

int Find_Answer() {
	for (int i = 1; i <= V; i++) {
		for (int j = 1; j <= 10; j++) {
			if (Yogurt[j] == i) {
				if ((Cost[0][i] == INF) || (YCost[j] == INF)) {
					continue;
				}
				if (Cost[0][i] <= YCost[j]) {
					return i;
				}
			}
		}
	}
	return -1;
}

int main() {
	FASTIO
	Input();
	Dijkstra(0, S);
	Settings();
	cout << Find_Answer() << "\n";

	return 0;
}