Submission #70471

#	Time	Username	Problem	Language	Result	Execution time	Memory
70471		Diuven	날다람쥐 (JOI14_ho_t4)	C++14	100 / 100	439 ms	140728 KiB

2014_ho_t4

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
const int MX=100010, inf=2e9;
const ll linf=2e17;

int n, m, h0, H[MX];
vector<pii> G[MX];

ll S[MX];

ll ans=linf;

void gozero(){
    ll D[MX];
    priority_queue<pli, vector<pli>, greater<pli>> Q;
    for(int i=1; i<=n; i++) D[i]=linf;
    D[1]=0; Q.push({0,1});
    while(!Q.empty()){
        int v=Q.top().second; ll d=Q.top().first; Q.pop();
        if(D[v]!=d) continue;
        for(pii &p:G[v]){
            int x,c; tie(x,c)=p;
            ll now=d+c;
            if(h0-now<0) continue;
            if(h0-now>H[x]) now=h0-H[x];
            if(now>=D[x]) continue;
            D[x]=now; Q.push({now,x});
        }
    }
    if(D[n]<=h0) ans=D[n]+H[n]-(h0-D[n]);

    for(int i=1; i<=n; i++) S[i]=linf;

    for(int i=1; i<=n; i++){
        if(h0<D[i]) continue;
        S[i]=min(S[i], D[i] + (h0-D[i]));
        for(pii &e:G[i]){
            int x,c; tie(x,c)=e;
            S[x]=min(S[x], D[i] + abs(h0-D[i]-c) + c);
        }
    }
    if(S[n]<linf) ans=min(ans, S[n]+H[n]);
    // for(int i=1; i<=n; i++) cout<<S[i]<<' ';
    // cout<<'\n';
}

ll solve(){
    ll D[MX];
    priority_queue<pli, vector<pli>, greater<pli>> Q;
    for(int i=1; i<=n; i++) D[i]=linf;
    for(int i=1; i<=n; i++)
        if(S[i]<linf) D[i]=S[i], Q.push({D[i], i});
    while(!Q.empty()){
        int v=Q.top().second; ll d=Q.top().first; Q.pop();
        if(D[v]!=d) continue;
        for(pii &e:G[v]){
            int x,c; tie(x,c)=e; c*=2;
            if(D[v]+c>=D[x]) continue;
            D[x]=D[v]+c; Q.push({D[x], x});
        }
    }
    // for(int i=1; i<=n; i++) cout<<D[i]<<' ';
    // cout<<'\n';
    return D[n]+H[n];
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>h0;
    for(int i=1; i<=n; i++) cin>>H[i];
    for(int i=1; i<=m; i++){
        int u, v, c; cin>>u>>v>>c;
        if(H[u]-c>=0) G[u].push_back({v,c});
        if(H[v]-c>=0) G[v].push_back({u,c});
    }
    gozero();
    ans=min(ans, solve());
    cout<<(ans>=linf ? -1 : ans);
    return 0;
}

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