fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define MOD 1000000007
  4. #define ll long long
  5. const ll INF = 1e18;
  6. struct Edge {
  7.     int to;
  8.     ll weight;
  9.     Edge(int t, ll w) : to(t), weight(w) {}
  10. };
  11. vector<vector<Edge>> adj;
  12. vector<ll> dist;
  13. vector<ll>parent;
  14. ll cnt=1;
  15. void dijkstra(int n, int source) {
  16.     dist.assign(n + 1, INF);
  17.     parent.assign(n+1,-1);
  18.     priority_queue<
  19.         pair<ll,int>,
  20.         vector<pair<ll,int>>,
  21.         greater<pair<ll,int>>
  22.     > pq;
  23.  
  24.     dist[source] = 0;
  25.     parent[source]=0;
  26.     pq.push({0, source});
  27.  
  28.     while (!pq.empty()) {
  29.         ll d = pq.top().first;
  30.         int u = pq.top().second;
  31.         pq.pop();
  32.  
  33.         if (d > dist[u]) continue;
  34.  
  35.         for (const Edge &e : adj[u]) {
  36.             int v = e.to;
  37.             ll w = e.weight;
  38.              if(dist[v]==dist[u]+w){
  39.                 cnt++;
  40.              }
  41.             if (dist[v] > dist[u] + w) {
  42.                 dist[v] = dist[u] + w;
  43.                 parent[v]=u;
  44.                 pq.push({dist[v], v});
  45.             }
  46.              }
  47.         }
  48.     }
  49.  
  50. int main() {
  51.     ios::sync_with_stdio(false);
  52.     cin.tie(nullptr);
  53.  
  54.     int n, m;
  55.     cin >> n >> m;
  56.  
  57.     adj.resize(m*n+5);
  58.     int arr1[2]={1,0};
  59.     int arr2[2]={0,1};
  60.     vector<int>arr(n*m+5);
  61.    for(int j=0;j<n;j++){
  62.     for (int i=0;i<m;i++){
  63.         int cord=j*m+i;
  64.         cin>>arr[cord];
  65.     }
  66. }
  67.     for(int j=0;j<n;j++){
  68.         for(int i=0;i<m;i++){
  69.             int cord=j*m+i;
  70.          for(int k=0;k<2;k++){
  71.             int dx=j+arr1[k];
  72.             int dy=i+arr2[k];
  73.             if(dx>=n||dx<0||dy>=m||dy<0)continue;
  74.             int cord2=dx*m+dy;
  75.             adj[cord].emplace_back(cord2,arr[cord2]);
  76.         }
  77.         }
  78.     }
  79.     int source=0;
  80.  
  81.    dijkstra(n*m,source);
  82.  
  83.     if(parent[n*m-1]==-1){
  84.       cout<<-1<<"\n";
  85.     }
  86.     else{
  87.         cout<<dist[n*m-1]+arr[0]<<"\n";
  88.     }
  89.  
  90.     return 0;
  91. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/2kcXIO
language:
C++14 (gcc 8.3)
created:
5 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!