[BOJ] 20160 - 야쿠르트 아줌마 야쿠르트 주세요

[백준] 20160 - 야쿠르트 아줌마 야쿠르트 주세요

단순하게 생각하면 된다. 나의 위치에서 다른 모든 지점까지의 거리를 한 번 구하고, 야쿠르트 아줌마가 출발하는 지점들에서 다른 지점까지의 거리를 구한다면 문제를 풀기 위해 필요한 모든 최단 경로를 알 수 있다.
이를 위해 다익스트라 알고리즘을 11번 수행함으로써 문제를 해결할 수 있다.

소스코드

#include <bits/stdc++.h>
#define INF 99999999999999
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;

int n;
bool ck[10005];
ll dist[10005];
vector<vector<PLL>> node;
priority_queue<PLL, vector<PLL>, greater<PLL>> mn;

ll go(int start, int end) {
	fill(dist, dist + n + 1, INF);
	memset(ck, 0, sizeof(ck));
	dist[start] = 0;
	mn.push(make_pair(0, start));
	while (!mn.empty()) {
		int f = mn.top().second;
		if (!ck[f]) {
			ck[f] = true;
			for (int h = 0; h < node[f].size(); h++) {
				if (dist[node[f][h].first] > dist[f] + node[f][h].second) {
					dist[node[f][h].first] = dist[f] + node[f][h].second;
					mn.push(make_pair(dist[node[f][h].first], node[f][h].first));
				}
			}
		}
		mn.pop();
	}
	return dist[end];
}

int main(void) {
	int e;
	scanf("%d %d", &n, &e);
	node.resize(n + 1);
	for (int i = 0; i < e; i++) {
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		node[u].push_back({ v, w });
		node[v].push_back({ u, w });
	}
	map<int, ll> distA;
	int start, prev;
	scanf("%d", &start);
	distA[start] = 0;
	prev = start;
	for (int i = 1; i < 10; i++) {
		int x;
		scanf("%d", &x);
		ll t = go(prev, x);
		if (t >= INF) continue;
		distA[x] = distA[prev] + t;
		prev = x;
	}
	int startNode;
	scanf("%d", &startNode);
	go(startNode, 1);
	int ans = -1;

	for (auto it = distA.begin(); it != distA.end(); it++) {
		if (it->second >= dist[it->first]) {
			if (ans == -1) {
				ans = it->first;
			}
			else {
				ans = min(ans, it->first);
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}