Submission #1521546
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) GET_MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
#define INF LONG_MAX/2-100
template<class T>
void dijkstra(const vector<vector<pair<int,T>>> &vec, vector<T> &d, int from=0){
using P = pair<T,int>;
fill(all(d), INF);
priority_queue<P, vector<P>, greater<P>> pq;
d[from] = 0;
pq.push(mp(0,from));
while(!pq.empty()){
auto p = pq.top(); pq.pop();
int v = p.second;
T dd = p.first;
if(d[v] < dd) continue;
for(auto to : vec[v]){
T nd = dd + to.second;
int ni = to.first;
if(d[ni] > nd){
d[ni] = nd;
pq.push(mp(nd, ni));
}
}
}
}
int main(){
map<char,int> ma = { {'N', 0},{'E', 1},{'S',2},{'W',3} };
int h,w,n,f;
cin>>h>>w>>n>>f;
int sx,sy,gx,gy;
cin>>sx>>sy>>gx>>gy;
sx--;sy--;gx--;gy--;
int si = -1;
vector<int> a(n),b(n),c(n),d(n),e(n);
rep(i,n){
string s;
cin>>a[i]>>b[i]>>s>>d[i]>>e[i];
a[i]--;
b[i]--;
c[i] = ma[s[0]];
if(a[i]==sx && b[i]==sy) si = i;
}
if(sx==gx && sy==gy){
cout << 0 << endl;
return 0;
}
using P = pair<int,long>;
vector<vector<pair<int,int>>> xx(h), yy(w); // pos, idx
vector<vector<P>> vec(5*n+1);
rep(i,n){
rep(j,4){
vec[5*i].pb(mp(5*i+j+1, (c[i]==j)?0:e[i]));
}
xx[a[i]].pb(mp(b[i]+d[i], 5*i+2));
xx[a[i]].pb(mp(b[i]-d[i], 5*i+4));
yy[b[i]].pb(mp(a[i]-d[i], 5*i+1));
yy[b[i]].pb(mp(a[i]+d[i], 5*i+3));
}
xx[gx].pb(mp(gy, 5*n));
yy[gy].pb(mp(gx, 5*n));
rep(i,h) if(xx[i].size()){
sort(all(xx[i]));
rep(j,xx[i].size()-1){
int p = xx[i][j].second, q = xx[i][j+1].second;
long wi = (long)f*(xx[i][j+1].first - xx[i][j].first);
vec[p].pb(mp(q, wi));
vec[q].pb(mp(p, wi));
}
}
rep(i,w) if(yy[i].size()){
sort(all(yy[i]));
rep(j,yy[i].size()-1){
int p = yy[i][j].second, q = yy[i][j+1].second;
long wi = (long)f*(yy[i][j+1].first - yy[i][j].first);
vec[p].pb(mp(q, wi));
vec[q].pb(mp(p, wi));
}
}
rep(i,n){
int idx = upper_bound(all(xx[a[i]]), mp(b[i], 0)) - xx[a[i]].begin();
vec[xx[a[i]][idx].second].pb(mp(5*i, f*abs<long>(b[i] - xx[a[i]][idx].first)));
idx--;
vec[xx[a[i]][idx].second].pb(mp(5*i, f*abs<long>(b[i] - xx[a[i]][idx].first)));
idx = upper_bound(all(yy[b[i]]), mp(a[i], 0)) - yy[b[i]].begin();
vec[yy[b[i]][idx].second].pb(mp(5*i, f*abs<long>(a[i] - yy[b[i]][idx].first)));
idx--;
vec[yy[b[i]][idx].second].pb(mp(5*i, f*abs<long>(a[i] - yy[b[i]][idx].first)));
}
vector<long> dist(5*n+1);
// rep(i,11)dbg(i,vec[i]);
dijkstra(vec, dist, si*5);
// dbg(dist);
if(dist[5*n]==INF) cout << -1 << endl;
else cout << dist[5*n] << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Find the Route! |
User |
tossy |
Language |
C++14 (GCC 5.4.1) |
Score |
190 |
Code Size |
3662 Byte |
Status |
WA |
Exec Time |
370 ms |
Memory |
47988 KB |
Judge Result
Set Name |
Subtask1 |
Subtask2 |
Subtask3 |
Subtask4 |
Score / Max Score |
190 / 190 |
0 / 170 |
0 / 360 |
0 / 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 |
1 ms |
256 KB |
sub1_in2.txt |
AC |
1 ms |
384 KB |
sub1_in3.txt |
AC |
2 ms |
384 KB |
sub2_in1.txt |
WA |
1 ms |
256 KB |
sub2_in2.txt |
AC |
3 ms |
640 KB |
sub2_in3.txt |
AC |
8 ms |
1408 KB |
sub3_in1.txt |
AC |
7 ms |
1280 KB |
sub3_in2.txt |
AC |
295 ms |
39540 KB |
sub3_in3.txt |
AC |
299 ms |
41844 KB |
sub3_in4.txt |
AC |
370 ms |
47988 KB |
sub4_in1.txt |
AC |
172 ms |
25088 KB |
sub4_in2.txt |
AC |
308 ms |
39284 KB |
sub4_in3.txt |
AC |
304 ms |
39032 KB |
sub4_in4.txt |
AC |
315 ms |
42368 KB |
sub4_in5.txt |
AC |
187 ms |
46576 KB |