fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl "\n"
  4. #define int long long
  5. #define faster() ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  6. const int MOD = 1e9 + 7 ;
  7.  
  8. int n  , m  ;
  9. typedef pair<int,pair<int,int>> iii ;
  10. int a[505][505];
  11. int d[505][505];
  12.  
  13. int dx[4] = {-1, +0, +1, 0};
  14. int dy[4] = {+0, -1, +0, 1};
  15.  
  16. void Dijkstra(int i ,int j){
  17.     d[i][j] = a[i][j] ; //ban dau chi phi duong di la a[i][j]
  18.     priority_queue<iii , vector<iii> , greater<iii>> Q ;
  19.     Q.push({a[i][j] , {i , j}}); 
  20.     while(!Q.empty()){
  21.         iii p = Q.top() ; Q.pop(); 
  22.         int i1 = p.second.first ;
  23.         int j1 = p.second.second;
  24.         int chiPhi = p.first;
  25.         if(chiPhi > d[i1][j1]) continue ;
  26.         for(int k = 0 ; k < 4 ; k++){
  27.             int i2 = i1 + dx[k], j2 = j1 + dy[k];
  28.             if(i2 >=1 && i2 <= n && j2 >= 1 && j2 <= m){
  29.                 if(d[i2][j2] > d[i1][j1] + a[i2][j2]){
  30.                     d[i2][j2] = d[i1][j1] + a[i2][j2];
  31.                     Q.push({d[i2][j2], {i2 , j2}});
  32.                 }
  33.             }
  34.         }
  35.     }
  36.     cout << d[n][m] ;
  37.     // for(int i = 1 ; i <= n ; i++){
  38.     //     for(int j = 1 ; j <= m ; j++){
  39.     //         cout << d[i][j] << " ";
  40.     //     }
  41.     //     cout << endl;
  42.     // }
  43. }
  44.  
  45. void solve(){
  46.     cin >> n >> m ;
  47.     for(int i = 1 ; i <= n ; i++){
  48.         for(int j = 1 ; j <= m ; j++){
  49.             cin >> a[i][j];
  50.             d[i][j] = 1e9 ;
  51.         }
  52.     }
  53.     Dijkstra(1 , 1);
  54. }
  55.  
  56. signed main() {
  57.     faster(); 
  58.     int test = 1 ; 
  59.     // cin >> test ;
  60.     while(test--)   solve();
  61.     return 0;
  62. }
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
Success #stdin #stdout 0s 5600KB
comments (?)
stdin
copy 
6 7
0 3 6 0 5 9 1 
6 5 4 4 0 7 6 
4 0 2 1 5 6 1 
2 7 7 3 3 1 6 
4 4 9 6 9 7 2 
3 6 4 4 1 9 2
stdout
copy 
28
https://ideone.com/Za2JPx
language:
C++ (gcc 8.3)
created:
6 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!