Submission #684463

#	Time	Username	Problem	Language	Result	Execution time	Memory
684463		JooDdae	날다람쥐 (JOI14_ho_t4)	C++17	100 / 100	199 ms	25292 KiB

2014_ho_t4

#include <bits/stdc++.h>
using namespace std;
using ll = long long;


const ll INF = 1e18;
int n, m, X;
ll h[100100];
vector<array<int, 2>> v[300300];

ll d1[100100];
priority_queue<array<ll, 2>> pq;

ll d2[100100];

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> X;
    for(int i=1;i<=n;i++) cin >> h[i];
    for(int i=1;i<=m;i++) {
        int a, b, c; cin >> a >> b >> c;
        v[a].push_back({b, c}), v[b].push_back({a, c});
    }

    memset(d1, -1, sizeof d1);
    d1[1] = X; pq.push({X, 1});
    while(!pq.empty()) {
        auto [c, u] = pq.top(); pq.pop();
        if(c < d1[u]) continue;
        for(auto [x, y] : v[u]) if(d1[x] < min(h[x], c-y)) d1[x] = min(h[x], c-y), pq.push({d1[x], x});
    }
    
    if(d1[n] > -1) return cout << X-d1[n] + h[n]-d1[n], 0;


    for(int i=1;i<=n;i++) d2[i] = (d1[i] < 0 ? INF : X);

    for(int i=1;i<=n;i++) if(d1[i] > -1) {
        for(auto [x, y] : v[i]) if(h[i] >= y && y > d1[i]) d2[x] = min(d2[x], X-d1[i] + y-d1[i] + y);
    }

    for(int i=1;i<=n;i++) if(d2[i] < INF) pq.push({-d2[i], i});
    while(!pq.empty()) {
        auto [c, u] = pq.top(); pq.pop();
        if(-c > d2[u]) continue;
        for(auto [x, y] : v[u]) if(h[u] >= y && y+y-c < d2[x]) d2[x] = y+y-c, pq.push({-d2[x], x});
    }
    
    ll ans = d2[n] + h[n];
    cout << (ans >= INF ? -1 : ans);
}

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