직장인 파댕이의 사회생활 (백준 30985)

안녕하세요. 오늘은 사회생활을 할 거예요.

문제

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

아이디어

일단 엘리베이터는 한번만 타는게 이득입니다.
그래서 1->A->엘리베이터타고 꼭대기로->N이 가장 효육적입니다.
그러므로 1에서 모든곳까지의 최댄경로와 모든곳부터 N까지의 최단경로를 다 구해서 모든 지점에서의 위의 값을 구해서 최솟값을 출력해주면 됩니다.

소스코드

#include <iostream>
#include <vector>
#include <queue>
#define ll long long
using namespace std;

vector <pair <ll, ll> > graph[101010];
ll N, dp[2][101010] = { 0 };;

void dij(ll x)
{
    priority_queue <pair <ll, ll>, vector <pair <ll, ll> >, greater<> > q;

    ll node;
    if (x == 0) node = 1;
    else node = N;
    for (ll i = 1; i <= N; i++)
        dp[x][i] = 1e18;
    dp[x][node] = 0;
    q.push({ 0,node });
    while (q.size())
    {
        ll dis = q.top().first;
        ll curr = q.top().second;
        q.pop();
        if (dp[x][curr] < dis) continue;
        for (auto i : graph[curr])
        {
            ll d = i.second + dis;
            ll now = i.first;
            if (d < dp[x][now])
            {
                dp[x][now] = d;
                q.push({ d,now });
            }
        }
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll M, K, i, a, b, c, start;
    cin >> N >> M >> K;
    for (i = 0; i < M; i++)
    {
        cin >> a >> b >> c;
        graph[a].push_back({ b,c });
        graph[b].push_back({a,c});
    }
    dij(0); dij(1);

    ll mn = 1e18;
    for (i = 1; i <= N; i++)
    {
        ll x;
        cin >> x;
        if (x == -1) continue;
        mn = min(mn, x * (K - 1) + dp[0][i] + dp[1][i]);
    }
    if (mn != 1e18) cout << mn;
    else cout << -1;
}

감사합니다.