제출 #1247892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247892		tvgk	날다람쥐 (JOI14_ho_t4)	C++20	100 / 100	181 ms	20796 KiB

2014_ho_t4

#include<bits/stdc++.h>
using namespace std;
#define task "RABBIT"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 1e5 + 7;
const ll inf = 1e18 + 7;

int n, m, stt, h[mxN], mx[mxN];
vector<ii> w[mxN];
ll dp[mxN];

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

    cin >> n >> m >> stt;
    for (int i = 1; i <= n; i++)
    {
        dp[i] = inf;
        mx[i] = -1;
        cin >> h[i];
    }

    for (int i = 1; i <= m; i++)
    {
        int u, v, t;
        cin >> u >> v >> t;
        w[u].push_back({v, t});
        w[v].push_back({u, t});
    }

    priority_queue<ii, vector<ii>, greater<ii>> pq;
    pq.push({0, 1});
    mx[1] = stt;
    dp[1] = 0;
    while (pq.size())
    {
        ii j = pq.top();
        pq.pop();

        if (j.fi != dp[j.se])
            continue;

        for (ii i : w[j.se])
        {
            if (i.se > h[j.se])
                continue;

            int nw = max(0LL, mx[j.se] - i.se);
            ll val = j.fi + i.se + max(0LL, i.se - mx[j.se]);
            if (nw > h[i.fi])
                val += nw - h[i.fi];

            if (val < dp[i.fi])
            {
                mx[i.fi] = min(nw, h[i.fi]);
                dp[i.fi] = val;
                pq.push({dp[i.fi], i.fi});
            }
        }
    }
    if (mx[n] == -1)
        cout << -1;
    else
        cout << dp[n] + h[n] - mx[n];
}

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