Submission #1292425
Source Code Expand
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
struct q_t
{
int idx;
ll cost;
bool operator<(const q_t& rhs) const
{
return cost>rhs.cost;
}
};
priority_queue<q_t> que;
void push(q_t q)
{
que.push(q);
}
int pop(q_t& q)
{
if(que.empty()) return 0;
q=que.top();
que.pop();
return 1;
}
template<typename T>
vector<vector<T> > vv_alloc(int w, int h, const T& f=T())
{
vector<vector<T> > ret;
ret.resize(h);
for(auto& x : ret) x.resize(w, f);
return ret;
}
struct vert_t
{
int x, y;
int dir, distance;
int dir_cost;
ll cost;
};
int h, w, f;
int calc_dir(int x, int y)
{
if(x>0) return 'E';
if(x<0) return 'W';
if(y>0) return 'S';
return 'N';
}
int rev_dir(int dir)
{
switch(dir)
{
case 'N': return 'S';
case 'S': return 'N';
case 'E': return 'W';
case 'W': return 'E';
}
return '-';
}
int min_u(ll& m, ll v)
{
if(m<0 || m>v)
{
m=v;
return 1;
}
return 0;
}
ll calc(vert_t& v, int x, int y)
{
ll ret;
int dx, dy, ndir;
dx=x-v.x;
dy=y-v.y;
ndir=calc_dir(dx, dy);
if(v.dir==ndir)
{
ret=(ll)abs(abs(dx)+abs(dy)-v.distance)*f;
}
else
{
ret=(ll)abs(abs(dx)+abs(dy)-v.distance)*f+v.dir_cost;
if(rev_dir(v.dir)==ndir)
{
min_u(ret, (ll)abs(abs(dx)+abs(dy)+v.distance)*f);
}
}
return ret;
}
int solve(vector<vert_t>& v, int s_idx, int g_idx)
{
vector<vector<pair<int,ll> > > node;
vvi vw, vh;
int n=v.size();
node.resize(n);
vw.resize(w+1);
vh.resize(h+1);
for(int i=0;i<n;i++)
{
vw[v[i].x].push_back(i);
vh[v[i].y].push_back(i);
}
for(int x=1;x<=w;x++)
{
int s=vw[x].size();
for(int i=0;i<s;i++)
{
int vwi=vw[x][i];
for(int j=i+1;j<s;j++)
{
int vwj=vw[x][j];
node[vwi].push_back(make_pair(vwj, calc(v[vwi], v[vwj].x, v[vwj].y)));
node[vwj].push_back(make_pair(vwi, calc(v[vwj], v[vwi].x, v[vwi].y)));
}
}
}
for(int y=1;y<=h;y++)
{
int s=vh[y].size();
for(int i=0;i<s;i++)
{
int vhi=vh[y][i];
for(int j=i+1;j<s;j++)
{
int vhj=vh[y][j];
node[vhi].push_back(make_pair(vhj, calc(v[vhi], v[vhj].x, v[vhj].y)));
node[vhj].push_back(make_pair(vhi, calc(v[vhj], v[vhi].x, v[vhi].y)));
}
}
}
q_t q={s_idx, 0};
min_u(v[s_idx].cost, 0);
push(q);
for(;pop(q);)
{
if(q.cost>=v[g_idx].cost && v[g_idx].cost>=0) break;
for(auto& ne:node[q.idx])
{
q_t nq={ne.first, ne.second+q.cost};
if(min_u(v[ne.first].cost, ne.second+q.cost))
{
push(nq);
}
}
}
return 1;
}
int main(void)
{
int n, sx, sy, gx, gy, s_idx, g_idx;
vector<vert_t> v;
while(scanf("%d%d%d%d%d%d%d%d", &h, &w, &n, &f, &sy, &sx, &gy, &gx)==8)
{
s_idx=-1;
g_idx=-1;
v.clear();
v.resize(n);
for(int i=0;i<n;i++)
{
int a, b, d, e, dir=0;
char c[1+1];
scanf("%d%d%1s%d%d", &a, &b, c, &d, &e);
dir=c[0];
if(b==gx && a==gy)
{
g_idx=i;
d=0;
e=0;
}
if(b==sx && a==sy)
{
s_idx=i;
}
v[i]=(vert_t){b, a, dir, d, e, -1};
}
if(g_idx<0)
{
g_idx=v.size();
v.push_back((vert_t){gx, gy, 'N', 1000000000, 1000000000, -1});
}
solve(v, s_idx, g_idx);
printf("%lld\n", v[g_idx].cost);
#if 0
for(auto ve:v)
{
printf("(x,y)=(%d,%d) %lld\n", ve.x, ve.y, ve.cost);
}
#endif
}
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Find the Route! |
User |
myanta |
Language |
C++14 (GCC 5.4.1) |
Score |
190 |
Code Size |
3627 Byte |
Status |
RE |
Exec Time |
2172 ms |
Memory |
950004 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:208:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%1s%d%d", &a, &b, c, &d, &e);
^
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 |
2 ms |
896 KB |
sub1_in3.txt |
AC |
2 ms |
1024 KB |
sub2_in1.txt |
RE |
98 ms |
256 KB |
sub2_in2.txt |
AC |
2 ms |
512 KB |
sub2_in3.txt |
AC |
5 ms |
2432 KB |
sub3_in1.txt |
AC |
3 ms |
640 KB |
sub3_in2.txt |
AC |
518 ms |
259452 KB |
sub3_in3.txt |
AC |
548 ms |
266744 KB |
sub3_in4.txt |
AC |
705 ms |
327668 KB |
sub4_in1.txt |
AC |
41 ms |
10012 KB |
sub4_in2.txt |
AC |
102 ms |
28972 KB |
sub4_in3.txt |
AC |
74 ms |
16556 KB |
sub4_in4.txt |
AC |
71 ms |
15732 KB |
sub4_in5.txt |
TLE |
2172 ms |
950004 KB |