Submission #11185548
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;
#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------
int H,W;
ll A,B,C;
int N;
int Y[101010],X[101010];
ll D[505][505];
ll D2[505][505][5];
void solve() {
int i,j,k,l,r,x,y; string s;
cin>>H>>W;
cin>>A>>B>>C;
cin>>N;
H++,W++;
FOR(y,H) FOR(x,W) D[y][x]=1LL<<60;
queue<int> Q;
FOR(i,N) {
cin>>Y[i]>>X[i];
D[Y[i]][X[i]]=0;
Q.push(Y[i]*1000+X[i]);
}
while(Q.size()) {
y=Q.front()/1000;
x=Q.front()%1000;
Q.pop();
int dd[4]={1,0,-1,0};
FOR(i,4) {
int ty=y+dd[i];
int tx=x+dd[i^1];
if(ty<0||ty>=H||tx<0||tx>=W) continue;
if(D[ty][tx]>D[y][x]+C) {
D[ty][tx]=D[y][x]+C;
Q.push(ty*1000+tx);
}
}
}
priority_queue<pair<ll,int>> PQ;
FOR(y,H) FOR(x,W) FOR(i,5) D2[y][x][i]=1LL<<60;
D2[Y[0]][X[0]][4]=0;
PQ.push({0,Y[0]*1000+X[0]+4000000});
while(PQ.size()) {
ll co=-PQ.top().first;
int id=PQ.top().second/1000000;
int cy=PQ.top().second%1000000/1000;
int cx=PQ.top().second%1000;
PQ.pop();
//cout<<cy<<cx<<id<<" "<<co<<endl;
if(cy==Y[N-1]&&cx==X[N-1]) {
cout<<co<<endl;
return;
}
if(D2[cy][cx][id]!=co) continue;
int dd[4]={1,0,-1,0};
if(id==4) {
FOR(i,4) {
if(D2[cy][cx][i]>co+B) {
D2[cy][cx][i]=co+B;
PQ.push({-D2[cy][cx][i],cy*1000+cx+i*1000000});
}
int ty=cy+dd[i];
int tx=cx+dd[i^1];
if(ty<0||ty>=H||tx<0||tx>=W) continue;
if(D2[ty][tx][4]>co+C) {
D2[ty][tx][4]=co+C;
PQ.push({-D2[ty][tx][4],ty*1000+tx+4000000});
}
}
}
else {
if(D2[cy][cx][4]>co+D[cy][cx]) {
D2[cy][cx][4]=co+D[cy][cx];
PQ.push({-D2[cy][cx][4],cy*1000+cx+4000000});
}
int ty=cy+dd[id];
int tx=cx+dd[id^1];
if(ty<0||ty>=H||tx<0||tx>=W) continue;
if(D2[ty][tx][id]>co+A) {
D2[ty][tx][id]=co+A;
PQ.push({-D2[ty][tx][id],ty*1000+tx+id*1000000});
}
}
}
}
int main(int argc,char** argv){
string s;int i;
if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
cout.tie(0); solve(); return 0;
}
Submission Info
Submission Time |
|
Task |
D - サッカー (Soccer) |
User |
kmjp |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2527 Byte |
Status |
AC |
Exec Time |
239 ms |
Memory |
18868 KB |
Judge Result
Set Name |
Subtask01 |
Subtask02 |
Subtask03 |
Score / Max Score |
5 / 5 |
30 / 30 |
65 / 65 |
Status |
|
|
|
Set Name |
Test Cases |
Subtask01 |
01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, sample-02, sample-03 |
Subtask02 |
02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, sample-02, sample-03, sample-04 |
Subtask03 |
01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt, 03-13.txt, 03-14.txt, 03-15.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
19 ms |
10872 KB |
01-02.txt |
AC |
2 ms |
4352 KB |
01-03.txt |
AC |
50 ms |
17264 KB |
01-04.txt |
AC |
26 ms |
14708 KB |
01-05.txt |
AC |
38 ms |
12032 KB |
02-01.txt |
AC |
26 ms |
14708 KB |
02-02.txt |
AC |
19 ms |
13688 KB |
02-03.txt |
AC |
68 ms |
17392 KB |
02-04.txt |
AC |
190 ms |
17136 KB |
02-05.txt |
AC |
74 ms |
17264 KB |
02-06.txt |
AC |
108 ms |
17648 KB |
02-07.txt |
AC |
50 ms |
16788 KB |
02-08.txt |
AC |
58 ms |
17648 KB |
02-09.txt |
AC |
16 ms |
13216 KB |
02-10.txt |
AC |
14 ms |
12408 KB |
02-11.txt |
AC |
106 ms |
18800 KB |
02-12.txt |
AC |
99 ms |
17648 KB |
02-13.txt |
AC |
83 ms |
18288 KB |
02-14.txt |
AC |
42 ms |
18544 KB |
02-15.txt |
AC |
14 ms |
13216 KB |
03-01.txt |
AC |
22 ms |
10496 KB |
03-02.txt |
AC |
161 ms |
17776 KB |
03-03.txt |
AC |
200 ms |
14708 KB |
03-04.txt |
AC |
145 ms |
14776 KB |
03-05.txt |
AC |
141 ms |
18032 KB |
03-06.txt |
AC |
204 ms |
18868 KB |
03-07.txt |
AC |
127 ms |
13312 KB |
03-08.txt |
AC |
194 ms |
13556 KB |
03-09.txt |
AC |
239 ms |
15480 KB |
03-10.txt |
AC |
106 ms |
13440 KB |
03-11.txt |
AC |
39 ms |
14744 KB |
03-12.txt |
AC |
98 ms |
17908 KB |
03-13.txt |
AC |
126 ms |
16880 KB |
03-14.txt |
AC |
26 ms |
13724 KB |
03-15.txt |
AC |
149 ms |
13440 KB |
sample-01.txt |
AC |
2 ms |
4352 KB |
sample-02.txt |
AC |
2 ms |
4352 KB |
sample-03.txt |
AC |
2 ms |
4352 KB |
sample-04.txt |
AC |
2 ms |
4352 KB |