fork download 
  1. #include<stdio.h>
  2. #include<queue>
  3. using namespace std;
  4. int D[121][121], a[121][121];
  5. int dx[16] = { 1,-1,0,0,3,2,1,0,-1,-2,-3,-2,-1,0,1,2 };
  6. int dy[16] = { 0,0,1,-1,0,1,2,3,2,1,0,-1,-2,-3,-2,-1 };
  7. struct xy {
  8. 	int x, y, k;
  9. 	bool operator<(const xy p)const { return k > p.k; }
  10. };
  11. int main() {
  12. 	int n, t;
  13. 	int i, j;
  14. 	scanf("%d%d", &n, &t);
  15. 	for (i = 0; i < n; i++) for (j = 0; j < n; j++)scanf("%d", &a[i][j]), D[i][j] = -1;
  16. 	D[0][0] = 0;
  17. 	priority_queue<xy>que;
  18. 	que.push({ 0,0,0 });
  19. 	while (!que.empty()) {
  20. 		xy nowxy = que.top();
  21. 		que.pop();
  22. 		int nowx = nowxy.x, nowy = nowxy.y;
  23. 		if (D[nowx][nowy] != nowxy.k)continue;
  24. 		for (i = 0; i < 16; i++) {
  25. 			int nextx = nowx + dx[i];
  26. 			int nexty = nowy + dy[i];
  27. 			if (nextx < 0 || nextx >= n || nowy < 0 || nowy >= n)continue;
  28. 			if (D[nextx][nexty] == -1 || D[nextx][nexty]>D[nowx][nowy] + t * 3 + a[nextx][nexty]) {
  29. 				D[nextx][nexty] = D[nowx][nowy] + t * 3 + a[nextx][nexty];
  30. 				que.push({ nextx,nexty,D[nextx][nexty] });
  31. 			}
  32. 		}
  33. 	}
  34. 	int x, y, ans = -1;
  35. 	x = y = n - 1;
  36. 	for (i = 0; i <= 2; i++) {
  37. 		for (j = 0; j <= 2; j++) {
  38. 			if (i + j >= 3)continue;
  39. 			if (x - i < 0 || y - j < 0)continue;
  40. 			if (ans == -1 || ans >(i + j)*t + D[x - i][y - j])ans = (i + j)*t + D[x - i][y - j];
  41. 		}
  42. 	}
  43. 	printf("%d", ans);
  44. 	return 0;
  45. }
Success #stdin #stdout 0s 4316KB
comments (?)
stdin 
4 2
30 92 36 10
38 85 60 16
41 13 5 68
20 97 13 80
stdout 
31
https://ideone.com/PDojQh
language:
C++ (gcc 8.3)
created:
6 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!