fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5.  
  6. const ll INF = 4e18;
  7.  
  8. int main() {
  9.     ios::sync_with_stdio(0);
  10.     cin.tie(0);
  11.  
  12.     int n, m;
  13.     ll w;
  14.     cin >> n >> m >> w;
  15.  
  16.     vector<vector<int>> a(n, vector<int>(m));
  17.  
  18.     for (int i = 0; i < n; i++)
  19.         for (int j = 0; j < m; j++)
  20.             cin >> a[i][j];
  21.  
  22.     int dx[] = {1, -1, 0, 0};
  23.     int dy[] = {0, 0, 1, -1};
  24.  
  25.     ll ans = INF, bst1 = INF, bst2 = INF;
  26.  
  27.     // BFS from start
  28.     {
  29.         vector<vector<ll>> d(n, vector<ll>(m, INF));
  30.  
  31.         if (a[0][0] != -1) {
  32.             queue<pair<int, int>> q;
  33.             q.push({0, 0});
  34.             d[0][0] = 0;
  35.  
  36.             while (!q.empty()) {
  37.                 auto [x, y] = q.front();
  38.                 q.pop();
  39.  
  40.                 if (a[x][y] > 0)
  41.                     bst1 = min(bst1, d[x][y] + (ll)a[x][y]);
  42.  
  43.                 for (int k = 0; k < 4; k++) {
  44.                     int nx = x + dx[k];
  45.                     int ny = y + dy[k];
  46.  
  47.                     if (nx < 0 || ny < 0 || nx >= n || ny >= m)
  48.                         continue;
  49.                     if (a[nx][ny] == -1)
  50.                         continue;
  51.                     if (d[nx][ny] != INF)
  52.                         continue;
  53.  
  54.                     d[nx][ny] = d[x][y] + w;
  55.                     q.push({nx, ny});
  56.                 }
  57.             }
  58.  
  59.             ans = d[n - 1][m - 1];
  60.         }
  61.     }
  62.  
  63.     // BFS from end
  64.     {
  65.         vector<vector<ll>> d(n, vector<ll>(m, INF));
  66.  
  67.         if (a[n - 1][m - 1] != -1) {
  68.             queue<pair<int, int>> q;
  69.             q.push({n - 1, m - 1});
  70.             d[n - 1][m - 1] = 0;
  71.  
  72.             while (!q.empty()) {
  73.                 auto [x, y] = q.front();
  74.                 q.pop();
  75.  
  76.                 if (a[x][y] > 0)
  77.                     bst2 = min(bst2, d[x][y] + (ll)a[x][y]);
  78.  
  79.                 for (int k = 0; k < 4; k++) {
  80.                     int nx = x + dx[k];
  81.                     int ny = y + dy[k];
  82.  
  83.                     if (nx < 0 || ny < 0 || nx >= n || ny >= m)
  84.                         continue;
  85.                     if (a[nx][ny] == -1)
  86.                         continue;
  87.                     if (d[nx][ny] != INF)
  88.                         continue;
  89.  
  90.                     d[nx][ny] = d[x][y] + w;
  91.                     q.push({nx, ny});
  92.                 }
  93.             }
  94.         }
  95.     }
  96.  
  97.     if (bst1 != INF && bst2 != INF)
  98.         ans = min(ans, bst1 + bst2);
  99.  
  100.     cout << (ans == INF ? -1 : ans);
  101.  
  102.     return 0;
  103. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
5 5 1
0 -1 0 1 -1
0 20 0 0 -1
-1 -1 -1 -1 -1
3 0 0 0 0
-1 0 0 0 0
stdout
copy 
14
https://ideone.com/DfgCJp
language:
C++ (gcc 8.3)
created:
57 minutes 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!