Submission #1293608

---

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


void solve_i(vector<vert_t>& v, vvi& vw, vector<vector<pair<int,ll> > >& node)
{
	for(int x=vw.size()-1;x>0;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)));
			}
		}
	}
}


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();
	q_t q;

	if(s_idx<0) return 0;
	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);
	}

	solve_i(v, vw, node);
	solve_i(v, vh, node);

printf("-1\n");
exit(0);

	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;
		for(auto& ne:node[q.idx])
		{
			q_t nq={ne.first, ne.second+q.cost};

			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

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:203: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