fork download 
  1. #include <bits/stdc++.h> 
  2. using namespace std;
  3.  
  4. const int INF = 1e9+7;
  5. const long long INFLL = 1e18+7;
  6. const int MAXN = 1e5+7;
  7. const vector <int> dx = {-1, +0, +0, +1, +0, +0}; 
  8. const vector <int> dy = {+0, -1, +0, +0, +1, +0};
  9. const vector <int> dz = {+0, +0, -1, +0, +0, +1};
  10.  
  11. int n;
  12. long long a[107][107][107];
  13. long long Dist[107][107][107];
  14. bool Check[107][107][107];
  15.  
  16. struct dimension{
  17. 	int x,y,z;
  18. 	dimension(int _x, int _y, int _z)
  19. 	{x = _x; y = _y; z = _z;}
  20. };
  21.  
  22. struct cmp
  23. {
  24. 	bool operator()(pair<int,dimension> &a, pair<int,dimension> &b)
  25. 	{
  26. 		return a.first > b.first;
  27. 	}
  28. };
  29.  
  30. bool check(int i, int j, int k)
  31. {
  32. 	return (1 <= i && i <= n && 1 <= j && j <= n && 1 <= k && k <= n);	
  33. }
  34.  
  35. long long Dijkstra(int si, int sj, int sk)
  36. {
  37. 	Dist[si][sj][sk] = 0;
  38. 	priority_queue<pair<int,dimension>, vector<pair<int,dimension>>, cmp> pq;
  39. 	pq.emplace(0,dimension(si,sj,sk));
  40.  
  41. 	while (!pq.empty())
  42. 	{
  43. 		dimension u = pq.top().second;
  44. 		pq.pop();
  45.  
  46. 		if (Check[u.x][u.y][u.z]) continue;
  47. 		Check[u.x][u.y][u.z] = 1;
  48.  
  49. 		for (int i = 0; i < 6; i++)
  50. 		{
  51. 			dimension v = dimension(u.x+dx[i], u.y+dy[i], u.z+dz[i]);
  52. 			long long w = a[v.x][v.y][v.z];
  53.  
  54. 			if (!check(v.x,v.y,v.z)) continue;
  55.  
  56. 			if (Dist[v.x][v.y][v.z] > Dist[u.x][u.y][u.z] + w)
  57. 			{
  58. 				Dist[v.x][v.y][v.z] = Dist[u.x][u.y][u.z] + w;
  59. 				pq.emplace(Dist[v.x][v.y][v.z],dimension(v.x,v.y,v.z));
  60. 			}
  61. 		}
  62. 	}
  63. 	return Dist[n][n][n];
  64. }
  65.  
  66. int main()
  67. {
  68.   ios_base::sync_with_stdio(false);
  69.   cin.tie(nullptr);
  70.  
  71. 	cin >> n;
  72. 	for (int i = 1; i <= n; i++)
  73. 		for (int j = 1; j <= n; j++)
  74. 			for (int k = 1; k <= n; k++)
  75. 				cin >> a[i][j][k];
  76.  
  77. 	for (int i = 1; i <= n; i++)
  78. 		for (int j = 1; j <= n; j++)
  79. 			for (int k = 1; k <= n; k++)
  80. 				Dist[i][j][k] = INFLL;
  81.  
  82. 	cout << Dijkstra(1,1,1);
  83.  
  84.   return 0;
  85. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/p3SqCt
language:
C++ (gcc 8.3)
created:
2 days 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!