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
AC × 3
AC × 3
AC × 10
AC × 14
TLE × 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 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