Submission #517219

#	Time	Username	Problem	Language	Result	Execution time	Memory
517219		azberjibiou	날다람쥐 (JOI14_ho_t4)	C++17	100 / 100	182 ms	25608 KiB

2014_ho_t4

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pdd pair<double, double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pmax pair<__int128, __int128>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=100020;
const int mxM=2500000;
const int mxK=105;
const int MOD=1000000007;
const ll INF=1000000000000000001;
int N, M;
ll X;
ll H[mxN];
vector <pll> v[mxN];
ll dis[2*mxN];
bool Chk[2*mxN];
priority_queue <pll> pq;
ll ans;
int main()
{
    gibon
    cin >> N >> M >> X;
    for(int i=1;i<=N;i++)   cin >> H[i];
    for(int i=0;i<M;i++)
    {
        int a, b, t;
        cin >> a >> b >> t;
        if(H[a]>=t) v[a].emplace_back(b, t);
        if(H[b]>=t) v[b].emplace_back(a, t);
    }
    for(int i=1;i<=2*N;i++) dis[i]=INF;
    dis[1]=0;
    pq.push({0, 1});
    while(!pq.empty())
    {
        int now=pq.top().sec;
        pq.pop();
        if(Chk[now])    continue;
        Chk[now]=true;
        if(now<=N)
        {
            if(dis[N+now]>X)
            {
                dis[N+now]=X;
                pq.push({-X, N+now});
            }
            for(pll nxt : v[now])
            {
                if(X>dis[now]+nxt.sec)
                {
                    if(dis[nxt.fir]>max(dis[now]+nxt.sec, X-H[nxt.fir]))
                    {
                        dis[nxt.fir]=max(dis[now]+nxt.sec, X-H[nxt.fir]);
                        pq.push({-dis[nxt.fir], nxt.fir});
                    }
                }
                else if(dis[nxt.fir+N]>2*nxt.sec-X+2*dis[now])
                {
                    dis[nxt.fir+N]=2*nxt.sec-X+2*dis[now];
                    pq.push({-dis[nxt.fir+N], nxt.fir+N});
                }
            }
        }
        else
        {
            for(pll nxt : v[now-N])
            {
                if(dis[N+nxt.fir]>dis[now]+2*nxt.sec)
                {
                    dis[N+nxt.fir]=dis[now]+2*nxt.sec;
                    pq.push({-dis[N+nxt.fir], N+nxt.fir});
                }
            }
        }
    }
    ans=min(dis[2*N]+H[N], 2*dis[N]+H[N]-X);
    cout << (ans>=INF ? -1 : ans);
}

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