fork download 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. template<typename T>
  12. bool minimize(T& a, const T& b) {
  13. 	if (b < a) {a = b; return true;}
  14. 	return false; 
  15. }
  16.  
  17. const int N = 2222; 
  18. const int M = 10;  
  19. const int MX = N * M + 5; 
  20.  
  21. int n, m;  
  22. vector<ii> adj[MX]; 
  23.  
  24. // Toạ độ 1D tương ứng với toạ độ (i, j)
  25. int getIndex(int i, int j) {
  26. 	return (i - 1) * m + j; 
  27. }
  28.  
  29. void addEdge(int u, int v, int w) {
  30. 	adj[u].push_back({v, w}); 
  31. 	adj[v].push_back({u, w}); 
  32. }
  33.  
  34. struct Node {
  35. 	int u; ll d; 
  36. 	bool operator<(const Node& other) const {
  37. 		return d > other.d; 
  38. 	}
  39. }; 
  40.  
  41. ll dist[MX]; // dist[u] = Đường đi ngắn nhất từ s đến u
  42.  
  43. void dijkstra(int s) {
  44. 	for (int u = 0; u <= n * m; u++) dist[u] = LINF; 
  45.  
  46. 	priority_queue<Node> pq; 
  47. 	dist[s] = 0;   
  48. 	pq.push({s, dist[s]});  
  49.  
  50. 	while (!pq.empty()) {
  51. 		Node front = pq.top(); pq.pop();  
  52. 		int u = front.u; ll d = front.d; 
  53.  
  54. 		if (d > dist[u]) continue; 
  55.  
  56. 		for (ii v : adj[u]) {
  57. 			if (minimize(dist[v.first], dist[u] + v.second)) {
  58. 				pq.push({v.first, dist[v.first]}); 
  59. 			}
  60. 		}
  61. 	}
  62. }
  63.  
  64. // Coi mỗi căn phòng là một đỉnh
  65. // Trọng số của cạnh nối giữa 2 đỉnh chính bằng chi phí để phá 
  66. // cánh cửa ngăn giữa 2 căn phòng tương ứng với 2 đỉnh đó
  67. int main() {
  68. 	ios::sync_with_stdio(false); 
  69. 	cin.tie(nullptr); 	
  70. 	cin >> n >> m; 
  71.  
  72. 	for (int j = 1; j <= m; j++) {
  73. 		int w; cin >> w;  
  74. 		addEdge(0, getIndex(1, j), w);  
  75. 	}
  76.  
  77. 	for (int i = 1; i <= n; i++) {
  78. 		for (int j = 1; j + 1 <= m; j++) {
  79. 			int w; cin >> w; 
  80. 			addEdge(getIndex(i, j), getIndex(i, j + 1), w); 
  81. 		}
  82.  
  83. 		if (i < n) {
  84. 			for (int j = 1; j <= m; j++) {
  85. 				int w; cin >> w; 
  86. 				addEdge(getIndex(i, j), getIndex(i + 1, j), w); 
  87. 			}
  88. 		}
  89. 	}
  90.  
  91. 	dijkstra(0); 
  92.  
  93. 	cout << dist[n * m] << '\n'; 
  94. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin 
4 2
99 10
1
10 99
1
99 10
1
10 99
1
stdout 
44
https://ideone.com/0wBtM6
language:
C++14 (gcc 8.3)
created:
287 days ago
visibility:
secret

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!