[BOJ] 20160번 : 야쿠르트 아줌마 야쿠르트 주세요 C++ 풀이

일단 다익스트라 응용 문제인 것은 간단하게? 눈치챌 수 있다. 

문제를 해석해보면, 아줌마는 총 10개의 노드를 순차적으로 이동한다고 한다. 여기서 문제의 핵심은 무조건 이 순서대로 이동한다는 것이다. 문제에서 주어지는 '나'의 순서는 필요없다. 그냥 모든 노드를 이동할 수 있고, 야쿠르트 아줌마를 만날 수 있는 노드가 몇번인지?를 구해야 한다.

아줌마가 이동할 노드들이 주어진다. 이때 각 노드별로 다익스트라를 돌려보자. 어차피 10번만 돌리면 되기 때문에, 10번의 다익스트라로 아줌마가 이동할 경로의 모든 최솟값 경로를 구할 수 있게 된다.

이제 나를 기준으로 다익스트라를 돌려주자.
내가 모든 노드에 도달할 수 있는 최소 비용을 구했다면, 이제 아줌마의 경로를 따라가봐야 한다.

아줌마가 i, i+1, i+2 ...로 이동할때 내가 i, i+1, i+2 ...로 이동하는 비용을 구하자. 이때 아줌마보다 빠르게 도달할 수 있는 i가 있다면 i 노드에서 야쿠르트를 받을 수 있게 된다. 그리고 이러한 노드들 중 최솟값을 찾으면 된다.

#include <bits/stdc++.h>
#define MINF 0x7f7f7f7f
#define INF 20000000000
#define MOD 10007
#define NUM 200010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
int V, E, S, answer = 1e9;
ll visited[11][10010];
vector<pll> adj[10010];
vector<int> v;

priority_queue<pii> pq;

void init() {
    for (int i=0; i<11; i++) for (int j=0; j<10010; j++) visited[i][j] = INF;
    cin >> V >> E;
    for (int i=0; i<E; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for (int i=1; i<=10; i++) {
        int x;
        cin >> x;
        v.push_back(x);
        visited[i][x] = 0;
        pq.push({0, x});
        while (!pq.empty()) {
            auto curr = pq.top();
            ll dist = -curr.X, node = curr.Y;
            pq.pop();
            if (visited[i][node] < dist) continue;
            for (auto next : adj[node]) {
                ll cost = dist + next.Y;
                int next_node = next.X;
                if (visited[i][next_node] <= cost) continue;
                visited[i][next_node] = cost;
                pq.push({-cost, next_node});
            }
        }
    }
    cin >> S;
    pq.push({0, S});
    visited[0][S] = 0;
    while (!pq.empty()) {
        auto curr = pq.top();
        ll dist = -curr.X, node = curr.Y;
        pq.pop();
        if (visited[0][node] < dist) continue;
        for (auto next : adj[node]) {
            ll cost = dist + next.Y;
            int next_node = next.X;
            if (visited[0][next_node] <= cost) continue;
            visited[0][next_node] = cost;
            pq.push({-cost, next_node});
        }
    }

    int s = 1;
    ll psum = 0;
    if (visited[0][v[0]] == 0) answer = v[0];
    for (int i=1; i<v.size(); i++) {
        int e = v[i];
        if (visited[s][e] == INF) continue;
        
        psum += visited[s][e];
        s = i+1;
        if (visited[0][e] <= psum) answer = min(answer, e);
    } 

    if (answer == 1e9) answer = -1;
    cout << answer << '\n';
}       

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    init();
}