Submission #1214471
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 |
151 ms |
Memory |
57832 KB |
Judge Result
Set Name |
Subtask1 |
Subtask2 |
Subtask3 |
Subtask4 |
Score / Max Score |
190 / 190 |
170 / 170 |
360 / 360 |
430 / 430 |
Status |
|
|
|
|
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 |
12 ms |
37632 KB |
sub1_in2.txt |
AC |
12 ms |
37632 KB |
sub1_in3.txt |
AC |
12 ms |
37632 KB |
sub2_in1.txt |
AC |
4 ms |
10496 KB |
sub2_in2.txt |
AC |
13 ms |
37632 KB |
sub2_in3.txt |
AC |
14 ms |
37888 KB |
sub3_in1.txt |
AC |
14 ms |
37760 KB |
sub3_in2.txt |
AC |
70 ms |
44656 KB |
sub3_in3.txt |
AC |
97 ms |
49900 KB |
sub3_in4.txt |
AC |
151 ms |
49516 KB |
sub4_in1.txt |
AC |
53 ms |
40824 KB |
sub4_in2.txt |
AC |
96 ms |
45940 KB |
sub4_in3.txt |
AC |
89 ms |
42868 KB |
sub4_in4.txt |
AC |
93 ms |
42360 KB |
sub4_in5.txt |
AC |
144 ms |
57832 KB |