Submission #95752

#	Time	Username	Problem	Language	Result	Execution time	Memory
95752		easrui	날다람쥐 (JOI14_ho_t4)	C++14	0 / 100	166 ms	13696 KiB

2014_ho_t4

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef pair<int,int> pii;
const int MN = 1e5+5;
int N,M,X,H[MN],a,b,t,pos;
long long len,dis,D[MN],h,ans;
vector<pii> G[MN];
struct node{
    int a;
    long long d;
    node(){};
    node(int x, long long 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();
        //cout << pos << ' ' << len << '\n';
        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;
                //cout << cur.vb << '\n';
                pq.push(node(cur.vb,dis));
            }
        }
    }
    ans = D[N]<H[1] ? 2*D[N]+H[N]-H[1] : D[N]+H[N];
    cout << ans;
}

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