fork(1) download
copy 
  1. #include<iostream>
  2. #include<tuple>
  3. #include<vector>
  4. #include<algorithm>
  5. #include<queue>
  6. #include<functional>
  7. using namespace std;
  8. int H, W, N, F, sx, sy, gx, gy, a[1000000], b[1000000], d[1000000], e[1000000], dist[660][660]; char c[1000000];
  9. pair<int, int>mae[660][660];
  10. vector<tuple<int, int, int>>x[660][660];
  11. int main() {
  12. 	cin >> H >> W >> N >> F;
  13. 	cin >> sx >> sy >> gx >> gy;
  14. 	for (int i = 0; i < N; i++) {
  15. 		cin >> a[i] >> b[i] >> c[i] >> d[i] >> e[i];
  16. 		for (int j = 1; j <= W; j++) {
  17. 			int cost = 0;
  18. 			if (c[i] == 'N' || c[i] == 'S')cost = abs(abs(j - b[i]) - d[i])*F + e[i];
  19. 			if (c[i] == 'E')cost = min(abs((j - b[i]) - d[i])*F, abs((j - b[i]) + d[i])*F + e[i]);
  20. 			if (c[i] == 'W')cost = min(abs((j - b[i]) - d[i])*F + e[i], abs((j - b[i]) + d[i])*F);
  21. 			x[a[i]][b[i]].push_back(make_tuple(a[i], j, cost));
  22. 		}
  23. 		for (int j = 1; j <= H; j++) {
  24. 			int cost = 0;
  25. 			if (c[i] == 'E' || c[i] == 'W')cost = abs(abs(j - a[i]) - d[i])*F + e[i];
  26. 			if (c[i] == 'S')cost = min(abs((j - a[i]) - d[i])*F, abs((j - a[i]) + d[i])*F + e[i]);
  27. 			if (c[i] == 'N')cost = min(abs((j - a[i]) - d[i])*F + e[i], abs((j - a[i]) + d[i])*F);
  28. 			x[a[i]][b[i]].push_back(make_tuple(j, b[i], cost));
  29. 		}
  30. 	}
  31. 	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>>Q;
  32. 	for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++)dist[i][j] = 1999999999; }
  33. 	Q.push(make_tuple(0, sx, sy)); dist[sx][sy] = 0;
  34. 	while (!Q.empty()) {
  35. 		int a1 = get<0>(Q.top()), a2 = get<1>(Q.top()), a3 = get<2>(Q.top()); Q.pop();
  36. 		for (int i = 0; i < x[a2][a3].size(); i++) {
  37. 			int to1 = get<0>(x[a2][a3][i]), to2 = get<1>(x[a2][a3][i]), cost = get<2>(x[a2][a3][i]);
  38. 			if (dist[to1][to2] > a1 + cost) {
  39. 				dist[to1][to2] = a1 + cost; Q.push(make_tuple(dist[to1][to2], to1, to2));
  40. 				mae[to1][to2] = make_pair(a2, a3);
  41. 			}
  42. 		}
  43. 	}
  44. 	int ret = dist[gx][gy];
  45. 	if (ret == 1999999999)ret = -1;
  46. 	vector<pair<int, int>>r1; int cx = gx, cy = gy;
  47. 	while (true) {
  48. 		if (mae[cx][cy] == make_pair(0, 0))break;
  49. 		r1.push_back(make_pair(cx, cy));
  50. 		pair<int, int>J = mae[cx][cy]; cx = J.first; cy = J.second;
  51. 	}
  52. 	reverse(r1.begin(), r1.end());
  53. 	cout << ret << endl;
  54. 	//for (int i = 0; i < r1.size(); i++)cout << r1[i].first << ' ' << r1[i].second << endl;
  55. 	return 0;
  56. }
Success #stdin #stdout 0s 47160KB
comments (?)
stdin
copy 
4 4 2 2
1 1 2 2
1 1 E 1 1
1 2 E 2 2
stdout
copy 
4
https://ideone.com/GmCVoD
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!