SHARE
TWEET

Untitled

a guest Aug 20th, 2019 57 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. inline ll rd() {ll x=0; bool neg=false; char c=getchar(); while(c!='-'&&(c<'0'||c>'9')) c=getchar(); if(c=='-') neg=true,c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar(); if(neg) x=-x; return x;}
  11. inline void write(ll x) {if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+48);}
  12. #define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
  13. #define read(x) x=rd()
  14.  
  15. const int N = 3e4 + 5;
  16. const ll INF = 1e18;
  17.  
  18. ll d[N];
  19. int n, m;
  20. vector <lli> adj[N];
  21.  
  22. void inp() {
  23.     read(m); read(n);
  24.     for (int i = 1; i <= m; i++) {
  25.         int w;
  26.         for (int j = 1; j <= n; j++) {
  27.             read(w);
  28.             adj[i*n + j].push_back(lli(w, (i - 1)*n + j));
  29.             adj[(i - 1)*n + j].push_back(lli(w, i*n + j));
  30.         }
  31.         for (int j = 1; j < n; j++) {
  32.             read(w);
  33.             adj[i*n + j].push_back(lli(w, i*n + j + 1));
  34.             adj[i*n + j + 1].push_back(lli(w, i*n + j));
  35.         }
  36.     }
  37. }
  38. void dijktra() {
  39.     priority_queue <lli, vector <lli>, greater <lli> > pq;
  40.     for (int i = 1; i <= n*m + n; i++) d[i] = INF;
  41.     d[m*n + n] = 0;
  42.     pq.push(lli(0, m*n + n));
  43.     while (pq.size()) {
  44.         lli t = pq.top();
  45.         pq.pop();
  46.         int u = t.se;
  47.         if (d[u] < t.fi) continue;
  48.         for (lli t: adj[u])
  49.             if (d[t.se] > d[u] + t.fi) {
  50.                 d[t.se] = d[u] + t.fi;
  51.                 pq.push(lli(d[t.se], t.se));
  52.             }
  53.     }
  54. }
  55. void out() {
  56.     write(*min_element(d + 1, d + n + 1));
  57. }
  58.  
  59. int main() {
  60.     fast_io;
  61.   //  freopen(taskname".INP", "r", stdin);
  62.   //  freopen(taskname".OUT", "w", stdout);
  63.     inp();
  64.     dijktra();
  65.     out();
  66. }
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
 
Top