Submission #95754

#	Time	Username	Problem	Language	Result	Execution time	Memory
95754		easrui	날다람쥐 (JOI14_ho_t4)	C++14	100 / 100	299 ms	25428 KiB

2014_ho_t4

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int MN = 1e5+5;
long long N,M,X,H[MN],a,b,t,pos,len,dis,D[MN],h,ans;
vector<pii> G[MN];
struct node{
    ll a,d;
    node(){};
    node(ll x, ll y){a = x, d = y;};
    bool operator < (const node &A) const{
        return A.d<d;
    }
};
priority_queue<node> pq;

int main()
{
    //freopen("input.txt","r",stdin);
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> N >> M >> X;
    for(int i=1; i<=N; i++) cin >> H[i];
    for(int i=0; i<M; i++){
        cin >> a >> b >> t;
        if(H[a]>=t) G[a].push_back(pii(t,b));
        if(H[b]>=t) G[b].push_back(pii(t,a));
    }
    for(int i=1; i<=N; i++) D[i] = 1e16;
    D[1] = 0;
    pq.push(node(1,0));
    while(!pq.empty()){
        pos = pq.top().a;
        len = pq.top().d;
        pq.pop();
        if(len>D[pos]) continue;
        for(pii cur : G[pos]){
            if(len<X){
                h = X - len;
                if(h<cur.va) dis = len + cur.va + (cur.va-h);
                else if(h>H[cur.vb]+cur.va) dis = X - H[cur.vb];
                else dis = len + cur.va;
            } else dis = len + 2*cur.va;
            if(dis<D[cur.vb]){
                D[cur.vb] = dis;
                pq.push(node(cur.vb,dis));
            }
        }
    }
    ans = D[N]+H[N]+min(D[N]-X,0ll);
    if(D[N]==1e16) ans = -1;
    cout << ans;
}

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