fork download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<tuple>
  5. #include<map>
  6. #include<queue>
  7. #include<functional>
  8. #include<string>
  9. using namespace std;
  10. #pragma warning(disable:4996)
  11.  
  12. long long H, W, N, F, sx, sy, gx, gy, a[200008], b[200008], d[200008], e[200008], dist[1000008][3]; char c[200008];
  13. vector<pair<int, int>> X[335008], Y[335008];
  14. vector<tuple<int, int, long long>> x[1000008][3];
  15. int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 }; char dz[6] = "NESW";
  16. vector<pair<int, int>>M[335008];
  17.  
  18. void Sorts() {
  19. 	for (int i = 0; i <= 335000; i++) {
  20. 		sort(M[i].begin(), M[i].end());
  21. 	}
  22. }
  23. int Find(int a1, int a2) {
  24. 	int pos1 = lower_bound(M[a1].begin(), M[a1].end(), make_pair(a2, 0)) - M[a1].begin();
  25. 	if (pos1 == M[a1].size())return 0;
  26. 	if (M[a1][pos1].first != a2)return 0;
  27. 	return M[a1][pos1].second;
  28. }
  29.  
  30. struct Edge {
  31. 	long long cost; int t1, t2;
  32. };
  33. bool operator<(Edge a1, Edge a2) {
  34. 	if (a1.cost < a2.cost)return true;
  35. 	return false;
  36. }
  37. bool operator>(Edge a1, Edge a2) {
  38. 	if (a1.cost > a2.cost)return true;
  39. 	return false;
  40. }
  41. int main() {
  42. 	cin >> H >> W >> N >> F >> sx >> sy >> gx >> gy;
  43. 	if(H>100000 || W>100000 || N>70000)return 0;
  44. 	if(sx<=0 || H<sx || sy<=0 || W<sy)return 0;
  45. 	sx += 105000; sy += 105000; gx += 105000; gy += 105000;
  46.  
  47. 	//---------------------------------------Step 1: Build Edges-------------------------------------
  48. 	long long t = N;
  49. 	for (int i = 0; i <= N; i++) {
  50. 		if (i < N) {
  51. 			char ch[4];
  52. 			scanf("%d%d%s%d%d", &a[i], &b[i], ch, &d[i], &e[i]);
  53. 			c[i] = ch[0]; a[i] += 105000; b[i] += 105000;
  54. 		}
  55. 		if (i == N) { a[i] = gx; b[i] = gy; }
  56. 		if (Find(a[i], b[i]) == 0) {
  57. 			M[a[i]].emplace_back(make_pair(b[i], i + 1));
  58. 			X[a[i]].emplace_back(make_pair(b[i], i)); Y[b[i]].emplace_back(make_pair(a[i], i));
  59. 		}
  60. 		else {
  61. 			if (i == N)t = Find(gx, gy) - 1;
  62. 		}
  63. 	}
  64. 	Sorts();
  65. 	if (sx == gx && sy == gy) { cout << "0" << endl; return 0; }
  66. 	if (Find(sx, sy) == 0) { cout << "-1" << endl; return 0; }
  67.  
  68. 	int cnt = N + 1;
  69. 	for (int i = 0; i < N; i++) {
  70. 		for (int j = 0; j < 4; j++) {
  71. 			long long cx = a[i] + dx[j] * d[i], cy = b[i] + dy[j] * d[i];
  72.  
  73. 			M[cx].emplace_back(make_pair(cy, cnt + 1));
  74. 			X[cx].emplace_back(make_pair(cy, cnt));
  75. 			Y[cy].emplace_back(make_pair(cx, cnt));
  76. 			cnt++;
  77. 		}
  78. 	}
  79. 	Sorts();
  80. 	for (int i = 0; i < N; i++) {
  81. 		for (int j = 0; j < 4; j++) {
  82. 			long long cx = a[i] + dx[j] * d[i], cy = b[i] + dy[j] * d[i];
  83. 			int PPP = Find(cx, cy);
  84.  
  85. 			long long U = e[i]; if (c[i] == dz[j])U = 0;
  86. 			x[i][2].emplace_back(make_tuple(PPP - 1, j % 2, U));
  87. 		}
  88. 		for (int j = 0; j < 2; j++)x[i][j].emplace_back(make_tuple(i, 2, 0));
  89. 	}
  90.  
  91. 	for (int i = 0; i <= 335000; i++) {
  92. 		sort(X[i].begin(), X[i].end());
  93. 		for (int j = 0; j < (int)X[i].size() - 1; j++) {
  94. 			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));
  95. 			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));
  96. 		}
  97. 	}
  98. 	for (int i = 0; i <= 335000; i++) {
  99. 		sort(Y[i].begin(), Y[i].end());
  100. 		for (int j = 0; j < (int)Y[i].size() - 1; j++) {
  101. 			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));
  102. 			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));
  103. 		}
  104. 	}
  105.  
  106. 	//------------------------------------------Step 2:Dijkstra--------------------------------------
  107. 	priority_queue<Edge, vector<Edge>, greater<Edge>> Q;
  108. 	for (int i = 0; i <= cnt; i++) { for (int j = 0; j < 3; j++)dist[i][j] = (1LL << 62); }
  109.  
  110. 	Q.push(Edge{ 0, Find(sx, sy) - 1, 2 }); dist[Find(sx, sy) - 1][2] = 0;
  111. 	while (!Q.empty()) {
  112. 		Edge a1 = Q.top(); Q.pop();
  113. 		if (a1.t1 == t) { cout << a1.cost << endl; return 0; }
  114.  
  115. 		for (tuple<int, int, long long> i : x[a1.t1][a1.t2]) {
  116. 			if (dist[get<0>(i)][get<1>(i)] > a1.cost + get<2>(i)) {
  117. 				dist[get<0>(i)][get<1>(i)] = a1.cost + get<2>(i);
  118. 				Q.push(Edge{ dist[get<0>(i)][get<1>(i)], get<0>(i), get<1>(i) });
  119. 			}
  120. 		}
  121. 	}
  122. 	long long ret = min({ dist[t][0],dist[t][1],dist[t][2] });
  123. 	if (ret == (1LL << 62))ret = -1;
  124. 	cout << ret << endl;
  125. 	return 0;
  126. }
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!