Submission #1293740
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;
}
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;
}
int min_cmp(ll a, ll b)
{
if(a<0) return 0;
return a<b;
}
ll calc(vert_t& cv, vert_t& nv)
{
ll ret;
int dx, dy, ndir;
dx=nv.x-cv.x;
dy=nv.y-cv.y;
ndir=calc_dir(dx, dy);
if(cv.dir==ndir)
{
ret=(ll)abs(abs(dx)+abs(dy)-cv.distance)*f;
}
else
{
ret=(ll)abs(abs(dx)+abs(dy)-cv.distance)*f+cv.dir_cost;
if(rev_dir(cv.dir)==ndir)
{
min_u(ret, (ll)abs(abs(dx)+abs(dy)+cv.distance)*f);
}
}
return ret;
}
int solve(vector<vert_t>& v, int s_idx, int g_idx)
{
vvi vw, vh;
int n=v.size();
q_t q;
if(s_idx<0) return 0;
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(;pop(q);)
;
push((q_t){s_idx, 0});
for(;pop(q);)
{
if(!min_u(v[q.idx].cost, q.cost)) continue;
if(min_cmp(v[g_idx].cost, q.cost)) break;
int cx=v[q.idx].x;
int cy=v[q.idx].y;
for(auto& nv:vw[cx])
{
if(nv==q.idx) continue;
q_t nq={nv, q.cost+calc(v[q.idx], v[nv])};
if(!min_cmp(v[nq.idx].cost, nq.cost))
{
push(nq);
}
}
for(auto& nv:vh[cy])
{
if(nv==q.idx) continue;
q_t nq={nv, q.cost+calc(v[q.idx], v[nv])};
if(!min_cmp(v[nq.idx].cost, nq.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;
char c[1+1];
scanf("%d%d%1s%d%d", &a, &b, c, &d, &e);
if(b==gx && a==gy)
{
g_idx=i;
}
if(b==sx && a==sy)
{
s_idx=i;
}
v[i]=(vert_t){b, a, c[0], d, e, -1};
}
if(g_idx<0)
{
g_idx=v.size();
v.push_back((vert_t){gx, gy, 'N', 1, 1, -1});
}
solve(v, s_idx, g_idx);
printf("%lld\n", v[g_idx].cost);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Find the Route! |
User |
myanta |
Language |
C++14 (GCC 5.4.1) |
Score |
720 |
Code Size |
2969 Byte |
Status |
TLE |
Exec Time |
2140 ms |
Memory |
1301076 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:190: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 |
170 / 170 |
360 / 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 |
256 KB |
sub1_in3.txt |
AC |
1 ms |
384 KB |
sub2_in1.txt |
AC |
1 ms |
256 KB |
sub2_in2.txt |
AC |
2 ms |
384 KB |
sub2_in3.txt |
AC |
3 ms |
1020 KB |
sub3_in1.txt |
AC |
2 ms |
384 KB |
sub3_in2.txt |
AC |
235 ms |
69728 KB |
sub3_in3.txt |
AC |
375 ms |
135648 KB |
sub3_in4.txt |
AC |
596 ms |
140772 KB |
sub4_in1.txt |
AC |
27 ms |
4892 KB |
sub4_in2.txt |
AC |
57 ms |
10540 KB |
sub4_in3.txt |
AC |
46 ms |
7212 KB |
sub4_in4.txt |
AC |
49 ms |
7668 KB |
sub4_in5.txt |
TLE |
2140 ms |
1301076 KB |