Submission #1214468


Source Code Expand

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int INF=1001001001001001001ll;
string latte="NESW";

int H,W,N,F;

pint to[111111][4];
pint to2[111111][4];
pint to3[111111][4];
int Y[111111],X[111111],D[111111],L[111111],E[111111];

vpint yo[111111];
vpint ta[111111];

int dist[111111][4][2];

signed main(){
    cin.tie(0);ios_base::sync_with_stdio(0);
    cin>>H>>W>>N>>F;
    int sy,sx,gy,gx;
    cin>>sy>>sx>>gy>>gx;
    sy--;sx--;gy--;gx--;

    if(sy==gy&&sx==gx){
        cout<<0<<endl;
        return 0;
    }
    int s=-1,g=-1;
    rep(i,N){
        char c;
        cin>>Y[i]>>X[i]>>c>>L[i]>>E[i];
        D[i]=find(all(latte),c)-latte.begin();
        Y[i]--;X[i]--;
        if(Y[i]==sy&&X[i]==sx)s=i;
        if(Y[i]==gy&&X[i]==gx)g=i;
    }

    if(s==-1){
        cout<<-1<<endl;
        return 0;
    }

    if(g==-1){
        Y[N]=gy;
        X[N]=gx;
        g=N;
        N++;
    }

    rep(i,N){
        yo[Y[i]].pb({X[i],i});
        ta[X[i]].pb({Y[i],i});
    }

    fill_n(*to,111111*4,pint(-1,-1));
    fill_n(*to2,111111*4,pint(-1,-1));
    fill_n(*to3,111111*4,pint(-1,-1));

    rep(i,H){
        sort(all(yo[i]));

        for(int j=0;j+1<yo[i].size();j++){
            int k=yo[i][j].se;
            int l=yo[i][j+1].se;
            to[k][1]=pint(l,yo[i][j+1].fi-yo[i][j].fi);
            to[l][3]=pint(k,yo[i][j+1].fi-yo[i][j].fi);
        }


        for(int j=0;j<yo[i].size();j++){
            int k=yo[i][j].se;
            int l=lower_bound(all(yo[i]),pint(yo[i][j].fi+L[k],-1))-yo[i].begin();
            if(l!=yo[i].size()){
                to2[k][1]=pint(yo[i][l].se,yo[i][l].fi-yo[i][j].fi-L[k]);
            }
            if(l!=0){
                l--;
                to3[k][1]=pint(yo[i][l].se,yo[i][j].fi+L[k]-yo[i][l].fi);
            }
        }

        for(int j=0;j<yo[i].size();j++){
            int k=yo[i][j].se;
            int l=upper_bound(all(yo[i]),pint(yo[i][j].fi-L[k]+1,-1))-yo[i].begin();
            l--;
            if(l!=-1){
                to2[k][3]=pint(yo[i][l].se,yo[i][j].fi-L[k]-yo[i][l].fi);
            }
            l++;
            if(l!=yo[i].size()){
                to3[k][3]=pint(yo[i][l].se,yo[i][l].fi-yo[i][j].fi+L[k]);
            }
        }
    }

    rep(i,W){
        sort(all(ta[i]));

        for(int j=0;j+1<ta[i].size();j++){
            int k=ta[i][j].se;
            int l=ta[i][j+1].se;
            to[k][2]=pint(l,ta[i][j+1].fi-ta[i][j].fi);
            to[l][0]=pint(k,ta[i][j+1].fi-ta[i][j].fi);
        }


        for(int j=0;j<ta[i].size();j++){
            int k=ta[i][j].se;
            int l=lower_bound(all(ta[i]),pint(ta[i][j].fi+L[k],-1))-ta[i].begin();
            if(l!=ta[i].size()){
                to2[k][2]=pint(ta[i][l].se,ta[i][l].fi-ta[i][j].fi-L[k]);
            }
            if(l!=0){
                l--;
                to3[k][2]=pint(ta[i][l].se,ta[i][j].fi+L[k]-ta[i][l].fi);
            }
        }

        for(int j=0;j<ta[i].size();j++){
            int k=ta[i][j].se;
            int l=upper_bound(all(ta[i]),pint(ta[i][j].fi-L[k]+1,-1))-ta[i].begin();
            l--;
            if(l!=-1){
                to2[k][0]=pint(ta[i][l].se,ta[i][j].fi-L[k]-ta[i][l].fi);
            }
            l++;
            if(l!=ta[i].size()){
                to3[k][0]=pint(ta[i][l].se,ta[i][l].fi-ta[i][j].fi+L[k]);
            }
        }
    }


    fill_n(**dist,111111*4*2,INF);
    dist[s][D[s]][0]=0;
    priority_queue<tuple<int,int,int,int>,vector<tuple<int,int,int,int>>,greater<tuple<int,int,int,int>>>que;
    que.push(make_tuple(0,s,D[s],0));

    while(que.size()){
        int c,v,d,t;
        tie(c,v,d,t)=que.top();
        que.pop();
        if(dist[v][d][t]<c)continue;

        if(v==g){
            cout<<c<<endl;
            return 0;
        }

        if(t==0){
            rep(i,4){
                if(dist[v][i][t]<=c+E[v])continue;
                dist[v][i][t]=c+E[v];
                que.push(make_tuple(dist[v][i][t],v,i,t));
            }

            if(to2[v][d].fi!=-1){
                int u=to2[v][d].fi;
                int len=to2[v][d].se;
                if(dist[u][d][1]>c+len*F){
                    dist[u][d][1]=c+len*F;
                    que.push(make_tuple(dist[u][d][1],u,d,1));
                }
            }
            if(to3[v][d].fi!=-1){
                int u=to3[v][d].fi;
                int len=to3[v][d].se;
                int nd=d^2;
                if(dist[u][nd][1]>c+len*F){
                    dist[u][nd][1]=c+len*F;
                    que.push(make_tuple(dist[u][nd][1],u,nd,1));
                }
            }
        }
        else{
            if(to[v][d].fi!=-1){
                int u=to[v][d].fi;
                int len=to[v][d].se;
                if(dist[u][d][t]>c+len*F){
                    dist[u][d][t]=c+len*F;
                    que.push(make_tuple(dist[u][d][t],u,d,t));
                }
            }

            if(dist[v][D[v]][0]>c){
                dist[v][D[v]][0]=c;
                que.push(make_tuple(c,v,D[v],0));
            }
        }
    }
    cout<<-1<<endl;

    return 0;
}

Submission Info

Submission Time
Task F - Find the Route!
User latte0119
Language C++14 (GCC 5.4.1)
Score 1150
Code Size 5689 Byte
Status AC
Exec Time 148 ms
Memory 57960 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 190 / 190 170 / 170 360 / 360 430 / 430
Status
AC × 3
AC × 3
AC × 10
AC × 15
Set Name Test Cases
Subtask1 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt
Subtask2 sub2_in1.txt, sub2_in2.txt, sub2_in3.txt
Subtask3 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt, sub3_in4.txt
Subtask4 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt, sub3_in4.txt, sub4_in1.txt, sub4_in2.txt, sub4_in3.txt, sub4_in4.txt, sub4_in5.txt
Case Name Status Exec Time Memory
sub1_in1.txt AC 11 ms 37632 KB
sub1_in2.txt AC 11 ms 37632 KB
sub1_in3.txt AC 11 ms 37632 KB
sub2_in1.txt AC 4 ms 10496 KB
sub2_in2.txt AC 12 ms 37632 KB
sub2_in3.txt AC 13 ms 37888 KB
sub3_in1.txt AC 13 ms 37760 KB
sub3_in2.txt AC 70 ms 45424 KB
sub3_in3.txt AC 89 ms 50156 KB
sub3_in4.txt AC 148 ms 49644 KB
sub4_in1.txt AC 49 ms 40824 KB
sub4_in2.txt AC 85 ms 45172 KB
sub4_in3.txt AC 76 ms 42868 KB
sub4_in4.txt AC 86 ms 42360 KB
sub4_in5.txt AC 139 ms 57960 KB