SHARE
TWEET

Untitled

a guest Aug 20th, 2019 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define taskname "TEST"
  5. typedef long long ll;
  6. typedef long double ld;
  7. typedef pair <ll, int> lli;
  8. #define fi first
  9. #define se second
  10. #define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
  11.  
  12. const int N = 3e4 + 5;
  13. const ll INF = 1e18;
  14.  
  15. ll d[N];
  16. int n, m;
  17. vector <lli> adj[N];
  18.  
  19. void inp() {
  20.     cin >> m >> n;
  21.     for (int i = 1; i <= m; i++) {
  22.         int w;
  23.         for (int j = 1; j <= n; j++) {
  24.             cin >> w;
  25.             adj[i*n + j].push_back(lli(w, (i - 1)*n + j));
  26.         }
  27.         for (int j = 1; j < n; j++) {
  28.             cin >> w;
  29.             adj[i*n + j].push_back(lli(w, i*n + j + 1));
  30.             adj[i*n + j + 1].push_back(lli(w, i*n + j));
  31.         }
  32.     }
  33. }
  34. void dijktra() {
  35.     priority_queue <lli, vector <lli>, greater <lli> > pq;
  36.     for (int i = 1; i <= n*m + n; i++) d[i] = INF;
  37.     d[m*n + n] = 0;
  38.     pq.push(lli(0, m*n + n));
  39.     while (pq.size()) {
  40.         lli t = pq.top();
  41.         pq.pop();
  42.         int u = t.se;
  43.         if (d[u] < t.fi) continue;
  44.         for (lli t: adj[u])
  45.             if (d[t.se] > d[u] + t.fi) {
  46.                 d[t.se] = d[u] + t.fi;
  47.                 pq.push(lli(d[t.se], t.se));
  48.             }
  49.     }
  50. }
  51. void out() {
  52.     cout << *min_element(d + 1, d + n + 1);
  53. }
  54.  
  55. int main() {
  56.     fast_io;
  57. //    freopen(taskname".INP", "r", stdin);
  58. //    freopen(taskname".OUT", "w", stdout);
  59.     inp();
  60.     dijktra();
  61.     out();
  62. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top