제출 #1276723

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

2014_ho_t4

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

const ll INF=1e18;
const int N=1e5+3;

int n, m, x, h[N];
vector<pair<int,int>> adj[N];
ll dist[N];

signed main(){

    cin>>n>>m>>x;
    for(int i=1;i<=n;i++)cin>>h[i];
    for(int i=1;i<=m;i++){
        int u, v, t;
        cin>>u>>v>>t;
        if(h[u] >= t) adj[u].push_back({v,t});
        if(h[v] >= t) adj[v].push_back({u,t});
    }
    fill(dist,dist+N,INF);
    priority_queue<pair<ll,int>> pq;
    dist[1] = 0, pq.push({0,1});
    while(!pq.empty()) {
        auto [d,a] = pq.top(); pq.pop(), d=-d;
        if(dist[a] < d) continue;
        for(auto [b,w] : adj[a]) {
            if(dist[a] < x) {
                if(x-dist[a] >= w) {
                    if(dist[b] > max(dist[a]+w,0LL+x-h[b])) {
                        dist[b] = max(dist[a]+w,0LL+x-h[b]);
                        pq.push({-dist[b],b});
                    }
                }else{
                    if(dist[b] > dist[a]+w+w-(x-dist[a])) {
                        dist[b] = dist[a]+w+w-(x-dist[a]);
                        pq.push({-dist[b],b});
                    }
                }
            }else if(dist[b] > dist[a]+2*w) {
                dist[b] = dist[a]+2*w;
                pq.push({-dist[b],b});
            }
        }
    }
    if(dist[n] < x)cout<<h[n]-(x-dist[n]) + dist[n]<<'\n';
    else if(h[n]+dist[n]>=INF)puts("-1");
    else cout<<h[n]+dist[n]<<'\n';
}

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