Submission #1087840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087840		jonghak9028	날다람쥐 (JOI14_ho_t4)	C++17	100 / 100	126 ms	26704 KiB

2014_ho_t4

/* ************************************************************************** */
/*                                                                            */
/*                                                      :::    :::    :::     */
/*   Problem Number: 10048                             :+:    :+:      :+:    */
/*                                                    +:+    +:+        +:+   */
/*   By: js9028 <boj.kr/u/js9028>                    +#+    +#+          +#+  */
/*                                                  +#+      +#+        +#+   */
/*   https://boj.kr/10048                          #+#        #+#      #+#    */
/*   Solved: 2024/09/13 17:30:05 by js9028        ###          ###   ##.kr    */
/*                                                                            */
/* ************************************************************************** */
#include<queue>
#include<vector>
#include<iostream>
#include<array>

using namespace std;
#define fastio (ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL))
typedef long long ll;
typedef long double lld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int MAXSIZE = 2000000;
const long long INF = 1e18 + 5;
const double EPSILON = 1e-14;
const ll DIV = 2000003;
const long double pi = 3.14159265358979323846264338327950288419716939937510L;

int n, m;
ll x;
ll hei[100055];
vector<pair<int, ll>> adj[100055];

ll dist[100055];

ll bfs()
{
    ll ans = INF;
    priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
    pq.push({ 0, 1, x });
    fill(dist, dist + n + 3, INF);
    dist[1] = 0;
    while (!pq.empty())
    {
        auto [d, cur, h] = pq.top();
        pq.pop();
        if (cur == n)
        {
            ans = min(ans, d + (hei[n] - h));
        }
        if (dist[cur] < d) continue;
        for (auto& nxt : adj[cur])
        {
            ll nd = dist[cur] + nxt.second;
            ll nh = h - nxt.second;
            if (nh < 0)
            {
                nd += -nh;
                nh = 0;
            }
            if (nh > hei[nxt.first])
            {
                nd += nh - hei[nxt.first];
                nh = hei[nxt.first];
            }

            if (dist[nxt.first] <= nd || hei[cur] < nxt.second)
                continue;
            dist[nxt.first] = nd;
            pq.push({ nd, nxt.first, nh });
        }
    }
    return ans == INF ? -1 : ans;
}

int main()
{
    fastio;
    cin >> n >> m >> x;
    for (int i = 1; i <= n; i++)
        cin >> hei[i];
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({ b, c });
        adj[b].push_back({ a, c });
    }
    cout << bfs();
    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 50 / 50