Submission #1521408


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 112000000012345678L

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;
  }

  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 = lower_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)));
    if(idx>0){
      idx--;
      vec[xx[a[i]][idx].second].pb(mp(5*i, f*abs<long>(b[i] - xx[a[i]][idx].first)));
    }

    idx = lower_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)));
    if(idx>0){
      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 3652 Byte
Status WA
Exec Time 374 ms
Memory 47348 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 190 / 190 0 / 170 0 / 360 0 / 430
Status
AC × 3
AC × 2
WA × 1
AC × 9
WA × 1
AC × 14
WA × 1
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 7 ms 1408 KB
sub3_in1.txt AC 6 ms 1280 KB
sub3_in2.txt AC 290 ms 40436 KB
sub3_in3.txt AC 305 ms 40692 KB
sub3_in4.txt AC 374 ms 47348 KB
sub4_in1.txt AC 168 ms 25088 KB
sub4_in2.txt AC 315 ms 39284 KB
sub4_in3.txt AC 303 ms 39032 KB
sub4_in4.txt AC 315 ms 42368 KB
sub4_in5.txt AC 187 ms 46576 KB