fork download
copy 
#include<iostream>
#include<algorithm>
#include<vector>
#include<tuple>
#include<map>
#include<queue>
#include<functional>
#include<string>
using namespace std;
#pragma warning(disable:4996)
 
long long H, W, N, F, sx, sy, gx, gy, a[200008], b[200008], d[200008], e[200008], dist[1000008][3]; char c[200008];
vector<pair<int, int>> X[335008], Y[335008];
vector<tuple<int, int, long long>> x[1000008][3];
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 }; char dz[6] = "NESW";
vector<pair<int, int>>M[335008];
 
void Sorts() {
	for (int i = 0; i <= 335000; i++) {
		sort(M[i].begin(), M[i].end());
	}
}
int Find(int a1, int a2) {
	int pos1 = lower_bound(M[a1].begin(), M[a1].end(), make_pair(a2, 0)) - M[a1].begin();
	if (pos1 == M[a1].size())return 0;
	if (M[a1][pos1].first != a2)return 0;
	return M[a1][pos1].second;
}
 
struct Edge {
	long long cost; int t1, t2;
};
bool operator<(Edge a1, Edge a2) {
	if (a1.cost < a2.cost)return true;
	return false;
}
bool operator>(Edge a1, Edge a2) {
	if (a1.cost > a2.cost)return true;
	return false;
}
int main() {
	cin >> H >> W >> N >> F >> sx >> sy >> gx >> gy;
	if(H>100000 || W>100000 || N>70000)return 0;
	if(sx<=0 || H<sx || sy<=0 || W<sy)return 0;
	sx += 105000; sy += 105000; gx += 105000; gy += 105000;
	
	//---------------------------------------Step 1: Build Edges-------------------------------------
	long long t = N;
	for (int i = 0; i <= N; i++) {
		if (i < N) {
			char ch[4];
			scanf("%d%d%s%d%d", &a[i], &b[i], ch, &d[i], &e[i]);
			c[i] = ch[0]; a[i] += 105000; b[i] += 105000;
		}
		if (i == N) { a[i] = gx; b[i] = gy; }
		if (Find(a[i], b[i]) == 0) {
			M[a[i]].emplace_back(make_pair(b[i], i + 1));
			X[a[i]].emplace_back(make_pair(b[i], i)); Y[b[i]].emplace_back(make_pair(a[i], i));
		}
		else {
			if (i == N)t = Find(gx, gy) - 1;
		}
	}
	Sorts();
	if (sx == gx && sy == gy) { cout << "0" << endl; return 0; }
	if (Find(sx, sy) == 0) { cout << "-1" << endl; return 0; }
 
	int cnt = N + 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 4; j++) {
			long long cx = a[i] + dx[j] * d[i], cy = b[i] + dy[j] * d[i];
			
			M[cx].emplace_back(make_pair(cy, cnt + 1));
			X[cx].emplace_back(make_pair(cy, cnt));
			Y[cy].emplace_back(make_pair(cx, cnt));
			cnt++;
		}
	}
	Sorts();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 4; j++) {
			long long cx = a[i] + dx[j] * d[i], cy = b[i] + dy[j] * d[i];
			int PPP = Find(cx, cy);
 
			long long U = e[i]; if (c[i] == dz[j])U = 0;
			x[i][2].emplace_back(make_tuple(PPP - 1, j % 2, U));
		}
		for (int j = 0; j < 2; j++)x[i][j].emplace_back(make_tuple(i, 2, 0));
	}
 
	for (int i = 0; i <= 335000; i++) {
		sort(X[i].begin(), X[i].end());
		for (int j = 0; j < (int)X[i].size() - 1; j++) {
			x[X[i][j].second][1].emplace_back(make_tuple(X[i][j + 1].second, 1, (X[i][j + 1].first - X[i][j].first)*F));
			x[X[i][j + 1].second][1].emplace_back(make_tuple(X[i][j].second, 1, (X[i][j + 1].first - X[i][j].first)*F));
		}
	}
	for (int i = 0; i <= 335000; i++) {
		sort(Y[i].begin(), Y[i].end());
		for (int j = 0; j < (int)Y[i].size() - 1; j++) {
			x[Y[i][j].second][0].emplace_back(make_tuple(Y[i][j + 1].second, 0, (Y[i][j + 1].first - Y[i][j].first)*F));
			x[Y[i][j + 1].second][0].emplace_back(make_tuple(Y[i][j].second, 0, (Y[i][j + 1].first - Y[i][j].first)*F));
		}
	}
 
	//------------------------------------------Step 2:Dijkstra--------------------------------------
	priority_queue<Edge, vector<Edge>, greater<Edge>> Q;
	for (int i = 0; i <= cnt; i++) { for (int j = 0; j < 3; j++)dist[i][j] = (1LL << 62); }
 
	Q.push(Edge{ 0, Find(sx, sy) - 1, 2 }); dist[Find(sx, sy) - 1][2] = 0;
	while (!Q.empty()) {
		Edge a1 = Q.top(); Q.pop();
		if (a1.t1 == t) { cout << a1.cost << endl; return 0; }
 
		for (tuple<int, int, long long> i : x[a1.t1][a1.t2]) {
			if (dist[get<0>(i)][get<1>(i)] > a1.cost + get<2>(i)) {
				dist[get<0>(i)][get<1>(i)] = a1.cost + get<2>(i);
				Q.push(Edge{ dist[get<0>(i)][get<1>(i)], get<0>(i), get<1>(i) });
			}
		}
	}
	long long ret = min({ dist[t][0],dist[t][1],dist[t][2] });
	if (ret == (1LL << 62))ret = -1;
	cout << ret << endl;
	return 0;
}
Success #stdin #stdout 0.03s 139008KB
comments (?)
stdin
copy 
5 5 7 10
1 2 4 5
1 2 E 2 6
2 3 S 2 7
3 1 N 1 8
3 2 W 1 10
4 1 E 4 12
5 5 N 3 13
5 1 E 2 14
stdout
copy 
14
https://ideone.com/TqXkj7
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!