Advertisement
BaoJIaoPisu

Untitled

Sep 28th, 2021
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.54 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define pb push_back
  5. #define pf push_front
  6. #define popb pop_back
  7. #define popf pop_front
  8. #define ins insert
  9. #define pq priority_queue
  10. #define minele min_element
  11. #define maxele max_element
  12. #define lb lower_bound //first pos >= val
  13. #define ub upper_bound // first pos > val
  14. #define cnt_bit __builtin_popcount
  15. #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  16. //#pragma GCC optimize("Ofast")
  17. //#pragma GCC target("avx,avx2,fma")
  18. using namespace std;
  19.  
  20. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  21.  
  22. typedef long long ll;
  23. typedef pair<ll, ll> pll;
  24. typedef pair<int, int> pii;
  25.  
  26.  
  27. int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
  28. int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  29. int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  30.  
  31. const ll oo = 1e18;
  32. const ll maxN = 1e6;
  33.  
  34. /* Author : Le Ngoc Bao Anh, 10A5, LQD High School for Gifted Student */
  35.  
  36. void maximize(int &a, int b) {
  37.     a = max(a, b);
  38. }
  39.  
  40. void minimize(int &a, int b) {
  41.     a = min(a, b);
  42. }
  43.  
  44. const int N = 2e5 + 10;
  45. struct P {
  46.     int x, y, id;
  47. } a[N];
  48. ll dp[N][2];
  49. vector<pii> g[N][2];
  50.  
  51. void solve() {
  52.     int n, m, k;
  53.     cin >> n >> m >> k;
  54.  
  55.     bool ok1 = false, ok2 = false;
  56.     for(int i = 1; i <= k; i++) {
  57.         cin >> a[i].x >> a[i].y; a[i].id = i;
  58.         if(a[i].x == 1 && a[i].y == 1) ok1 = true;
  59.         if(a[i].x == n && a[i].y == m) ok2 = true;
  60.     }
  61.  
  62.     a[++k] = {1, 1, k};
  63.     a[++k] = {n, m, k};
  64.     sort(a + 1, a + 1 + k, [&](P _a, P _b) {if(_a.x == _b.x) return _a.y < _b.y; return _a.x < _b.x;});
  65.     for(int i = 2; i <= k; i++) {
  66.         if(a[i].x == a[i - 1].x) {
  67.             g[a[i].id][0].pb(make_pair(a[i - 1].id, abs(a[i].y - a[i - 1].y)));
  68.             g[a[i - 1].id][0].pb(make_pair(a[i].id, abs(a[i].y - a[i - 1].y)));
  69.         }
  70.     }
  71.  
  72.     sort(a + 1, a + 1 + k, [&](P _a, P _b) {if(_a.y == _b.y) return _a.x < _b.x; return _a.y < _b.y;});
  73.     for(int i = 2; i <= k; i++) {
  74.         if(a[i].y == a[i - 1].y) {
  75.             g[a[i].id][1].pb(make_pair(a[i - 1].id, abs(a[i].x - a[i - 1].x)));
  76.             g[a[i - 1].id][1].pb(make_pair(a[i].id, abs(a[i].x - a[i - 1].x)));
  77.         }
  78.     }
  79.  
  80.     for(int i = 1; i <= k; i++) {
  81.         dp[i][0] = dp[i][1] = oo;
  82.     }
  83.  
  84.     dp[k - 1][0] = 0;
  85.     struct PQ {
  86.         int u, turn;
  87.         ll w;
  88.  
  89.         bool operator < (const PQ & temp) const {
  90.             return w >   temp.w;
  91.         }
  92.     };
  93.     pq<PQ> q;
  94.     q.push({k - 1, 0, 0});
  95.  
  96.     while(!q.empty()) {
  97.         PQ curr = q.top(); q.pop();
  98.         int u = curr.u, turn = curr.turn; ll f = curr.w;
  99.         if(u == k - 1) {
  100.             if(ok1 && dp[u][turn ^ 1] > dp[u][turn] + 1) {
  101.                 dp[u][turn ^ 1] = dp[u][turn] + 1;
  102.                 q.push({u, turn ^ 1, dp[u][turn ^ 1]});
  103.             }
  104.         } else
  105.         if(u == k) {
  106.             if(ok2 && dp[u][turn ^ 1] > dp[u][turn] + 1) {
  107.                 dp[u][turn ^ 1] = dp[u][turn] + 1;
  108.                 q.push({u, turn ^ 1, dp[u][turn ^ 1]});
  109.             }
  110.         } else
  111.         if(dp[u][turn ^ 1] > dp[u][turn] + 1) {
  112.             dp[u][turn ^ 1] = dp[u][turn] + 1;
  113.             q.push({u, turn ^ 1, dp[u][turn ^ 1]});
  114.         }
  115.  
  116.         for(int i = 0; i < g[u][turn].size(); i++) {
  117.             int v = g[u][turn][i].fi, w = g[u][turn][i].se;
  118.             if(dp[v][turn] > dp[u][turn] + w) {
  119.                 dp[v][turn] = dp[u][turn] + w;
  120.                 q.push({v, turn, dp[v][turn]});
  121.             }
  122.         }
  123.     }
  124.  
  125.     cout << (min(dp[k][0], dp[k][1]) < oo ? min(dp[k][0], dp[k][1]) : -1);
  126. }
  127.  
  128. int main()
  129. {
  130.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  131.     #ifndef ONLINE_JUDGE
  132.     freopen("input.txt", "r", stdin);
  133.     freopen("output.txt", "w", stdout);
  134.     #else
  135.     //online
  136.     #endif
  137.  
  138.     int tc = 1, ddd = 0;
  139.     // cin >> tc;
  140.     while(tc--) {
  141.         //ddd++;
  142.         //cout << "Case #" << ddd << ": ";
  143.         solve();
  144.     }
  145. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement