fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. const ll N = 1e6+5;
  5. const ll INF = 1e9+7;
  6.  
  7. vector<ll>vis(N, 0);
  8. vector<pair<ll, ll>>v[N];
  9. vector<ll>lvl(N, INF);
  10. ll n, m;
  11.  
  12. ll get_id(ll a, ll b, ll c){
  13. 	return a * c + b;
  14. }
  15.  
  16. void bfs(ll src, ll ww){
  17.  
  18. 	set<pair<ll,ll>> st;
  19. 	st.insert({ww, src});
  20. 	lvl[src] = ww;
  21. 	while(!st.empty()){
  22. 		auto dig = *st.begin();
  23. 		ll cc = dig.second;
  24. 		ll dd = dig.first;
  25. 		st.erase(st.begin());
  26. 		if(vis[cc]) continue;
  27. 		vis[cc] = 1;
  28. 		for(auto val : v[cc]){
  29. 			ll cur = val.first;
  30. 			ll wt = val.second;
  31. 			if(lvl[cc] + wt < lvl[cur]){
  32. 				lvl[cur] = lvl[cc] + wt;
  33. 				st.insert({lvl[cur], cur});
  34. 			}
  35. 		}
  36. 	}
  37. }
  38.  
  39. void solve(){
  40.  
  41. 	cin >> n >> m;
  42. 	ll grid [n][m];
  43. 	for(ll i = 0; i < n; ++i){
  44. 		for(ll j = 0; j < m; ++j){
  45. 			cin >> grid[i][j];
  46. 		}
  47. 	}
  48. 	ll uu, vv;
  49. 	for(ll i = 0; i < n; ++i){
  50. 		for(ll j = 0; j < m; ++j){
  51. 			if(j != m-1){
  52. 				uu = get_id(i, j, m);
  53. 				vv = get_id(i, j+1, m);
  54. 				v[uu].push_back({vv, grid[i][j+1]});
  55. 			}
  56. 			if(i != n-1){
  57. 				uu = get_id(i, j, m);
  58. 				vv = get_id(i+1, j, m);
  59. 				v[uu].push_back({vv, grid[i+1][j]});
  60. 			}
  61. 			if(j != 0){
  62. 				uu = get_id(i, j, m);
  63. 				vv = get_id(i, j-1, m);
  64. 				v[uu].push_back({vv, grid[i][j-1]});
  65. 			}
  66. 			if(i != 0){
  67. 				uu = get_id(i, j, m);
  68. 				vv = get_id(i-1, j, m);
  69. 				v[uu].push_back({vv, grid[i-1][j]});
  70. 			}
  71. 		}
  72. 	}
  73. 	bfs(0, grid[0][0]);
  74. 	ll dig = get_id(n-1, m-1, m);
  75. 	cout << lvl[dig] << endl;
  76. }
  77.  
  78. signed main(){
  79.  
  80. 	ll t;
  81. 	cin >> t;
  82. 	while(t--){
  83. 		for(ll i = 0; i < n * m; ++i){
  84. 			v[i].clear();
  85. 			lvl[i] = INF;
  86. 			vis[i] = 0;
  87.         }
  88. 		solve();
  89. 	}
  90. }
Success #stdin #stdout 0.02s 42108KB
comments (?)
stdin
copy 
2
4
5
0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
1
6
0 1 2 3 4 5
stdout
copy 
24
15
https://ideone.com/Z5fwFK
language:
C++14 (gcc 8.3)
created:
12 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!