fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define el '\n'
  4. #define fi first
  5. #define sec second
  6. #define pb push_back
  7. #define int long long
  8. #define pii pair<int,int>
  9. #define sz(v) (int)(v).size()
  10. #define all(v) (v).begin(),(v).end()
  11. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  12. #define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; i--)
  13.  
  14. using namespace std;
  15.  
  16. const int INF = 0x3f3f3f3f3f3f3f3f;
  17. const int MAX_K = 1e5;
  18.  
  19. pii a[MAX_K + 5];
  20. int n, k;
  21. pii st;
  22.  
  23. void Input(){
  24.     cin >> n >> k >> st.fi >> st.sec;
  25.     FOR(i, 1, k) cin >> a[i].fi >> a[i].sec;
  26. }
  27.  
  28. namespace sub12{
  29. //begin sub12
  30. bool check_sub(){
  31.     return k <= 10;
  32. }
  33.  
  34. const int K = 10;
  35. int dp[(1 << K) + 5][K + 5];
  36.  
  37. int get_dist(pii x, pii y){
  38.     if(x.fi == y.fi || x.sec == y.sec) return 0;
  39.     return min(abs(x.fi - y.fi), abs(x.sec - y.sec));
  40. }
  41.  
  42. int walk(pii x, pii y){
  43.     return abs(x.fi - y.fi) + abs(x.sec - y.sec);
  44. }
  45.  
  46. int get_ans(pii pos){
  47.     return min({walk(pos, {1, 1}),
  48.                walk(pos, {1, n}),
  49.                walk(pos, {n, 1}),
  50.                walk(pos, {n, n})});
  51. }
  52.  
  53. void Solve(){
  54.     FOR(i, 0, k - 1) a[i] = a[i + 1];
  55.  
  56.     memset(dp, 0x3f, sizeof(dp));
  57.     FOR(i, 0, k - 1) dp[1 << i][i] = get_dist(st, a[i]);
  58.  
  59.     vector<int> pos_one;
  60.     FOR(mask, 1, (1 << k) - 1){
  61.         FOR(bit, 0, k - 1) if(mask & (1 << bit)){
  62.             pos_one.pb(bit);
  63.         }
  64.  
  65.         for(int i : pos_one) for(int j : pos_one) if(i != j){
  66.             dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + get_dist(a[j], a[i]));
  67.         }
  68.         pos_one.clear();
  69.     }
  70.  
  71.     int ans = get_ans(st);
  72.     FOR(mask, 1, (1 << k) - 1) FOR(i, 0, k - 1){
  73.         ans = min(ans, dp[mask][i] + get_ans(a[i]));
  74.     }
  75.     cout << ans;
  76. }
  77. //end sub12
  78. }
  79.  
  80. namespace sub3{
  81. //begin sub3
  82. bool check_sub(){
  83.     return k <= 1000;
  84. }
  85.  
  86. int get_dist(pii x, pii y){
  87.     return min(abs(x.fi - y.fi), abs(x.sec - y.sec));
  88. }
  89.  
  90. int walk(pii x, pii y){
  91.     return abs(x.fi - y.fi) + abs(x.sec - y.sec);
  92. }
  93.  
  94. int dist_ans(pii pos){
  95.     return min({walk(pos, {1, 1}),
  96.                walk(pos, {1, n}),
  97.                walk(pos, {n, 1}),
  98.                walk(pos, {n, n})});
  99. }
  100.  
  101. vector<pii> g[MAX_K + 5];
  102. int dist[MAX_K + 5];
  103.  
  104. void dijkstra(){
  105.     memset(dist, 0x3f, sizeof(dist));
  106.     priority_queue<pii, vector<pii>, greater<pii>> pq;
  107.  
  108.     pq.push({0, 0});
  109.     dist[0] = 0;
  110.  
  111.     while(sz(pq)){
  112.         int len = pq.top().fi;
  113.         int u = pq.top().sec;
  114.         pq.pop();
  115.  
  116.         if(len > dist[u]) continue;
  117.         for(pii x : g[u]){
  118.             int v = x.fi, w = x.sec;
  119.             if(dist[v] > dist[u] + w){
  120.                 dist[v] = dist[u] + w;
  121.                 pq.push({dist[v], v});
  122.             }
  123.         }
  124.     }
  125. }
  126.  
  127. void Solve(){
  128.     FOR(u, 1, k){
  129.         g[0].pb({u, get_dist(st, a[u])});
  130.         g[u].pb({k + 1, dist_ans(a[u])});
  131.  
  132.         FOR(v, u + 1, k){
  133.             g[u].pb({v, get_dist(a[u], a[v])});
  134.             g[v].pb({u, get_dist(a[u], a[v])});
  135.         }
  136.     }
  137.  
  138.     g[0].pb({k + 1, dist_ans(st)});
  139.     dijkstra();
  140.     cout << dist[k + 1];
  141. }
  142. //end sub3
  143. }
  144.  
  145. namespace sub4{
  146. //begin sub4
  147. bool check_sub(){
  148.     return true;
  149. }
  150.  
  151. struct Node{
  152.     pii pos;
  153.     int id;
  154. }ar[MAX_K + 5];
  155.  
  156. int get_dist(pii x, pii y){
  157.     return min(abs(x.fi - y.fi), abs(x.sec - y.sec));
  158. }
  159.  
  160. int walk(pii x, pii y){
  161.     return abs(x.fi - y.fi) + abs(x.sec - y.sec);
  162. }
  163.  
  164. int dist_ans(pii pos){
  165.     return min({walk(pos, {1, 1}),
  166.                walk(pos, {1, n}),
  167.                walk(pos, {n, 1}),
  168.                walk(pos, {n, n})});
  169. }
  170.  
  171. vector<pii> g[MAX_K + 5];
  172. int dist[MAX_K + 5];
  173.  
  174. void dijkstra(){
  175.     memset(dist, 0x3f, sizeof(dist));
  176.     priority_queue<pii, vector<pii>, greater<pii>> pq;
  177.  
  178.     pq.push({0, 0});
  179.     dist[0] = 0;
  180.  
  181.     while(sz(pq)){
  182.         int len = pq.top().fi;
  183.         int u = pq.top().sec;
  184.         pq.pop();
  185.  
  186.         if(len > dist[u]) continue;
  187.         for(pii x : g[u]){
  188.             int v = x.fi, w = x.sec;
  189.             if(dist[v] > dist[u] + w){
  190.                 dist[v] = dist[u] + w;
  191.                 pq.push({dist[v], v});
  192.             }
  193.         }
  194.     }
  195. }
  196.  
  197. bool cmp_doc(const Node &x, const Node &y){
  198.    return (x.pos.fi < y.pos.fi);
  199. }
  200.  
  201. bool cmp_ngang(const Node &x, const Node &y){
  202.     return (x.pos.sec < y.pos.sec);
  203. }
  204.  
  205. void Solve(){
  206.     FOR(i, 1, k) ar[i] = {a[i], i};
  207.  
  208.     FOR(i, 1, k){
  209.         g[0].pb({ar[i].id, get_dist(st, ar[i].pos)});
  210.         g[ar[i].id].pb({k + 1, dist_ans(ar[i].pos)});
  211.     }
  212.  
  213.  
  214.     sort(ar + 1, ar + k + 1, cmp_doc);
  215.     FOR(i, 1, k - 1){
  216.         g[ar[i].id].pb({ar[i + 1].id, get_dist(ar[i].pos, ar[i + 1].pos)});
  217.         g[ar[i + 1].id].pb({ar[i].id, get_dist(ar[i].pos, ar[i + 1].pos)});
  218.     }
  219.  
  220.     sort(ar + 1, ar + k + 1, cmp_ngang);
  221.     FOR(i, 1, k - 1){
  222.         g[ar[i].id].pb({ar[i + 1].id, get_dist(ar[i].pos, ar[i + 1].pos)});
  223.         g[ar[i + 1].id].pb({ar[i].id, get_dist(ar[i].pos, ar[i + 1].pos)});
  224.     }
  225.  
  226.     g[0].pb({k + 1, dist_ans(st)});
  227.     dijkstra();
  228.     cout << dist[k + 1];
  229. }
  230. //end sub4
  231. }
  232.  
  233. signed main(){
  234.     freopen("GAME.INP", "r", stdin);
  235.     freopen("GAME.OUT", "w", stdout);
  236.     ios_base::sync_with_stdio(0);
  237.     cin.tie(0);
  238.  
  239.     Input();
  240.  
  241.     if(sub12::check_sub()) return sub12::Solve(), 0;
  242.     if(sub3::check_sub()) return sub3::Solve(), 0;
  243.     if(sub4::check_sub()) return sub4::Solve(), 0;
  244.  
  245.     return 0;
  246. }
  247.  
Success #stdin #stdout 0.01s 13156KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3lGu5f
language:
C++ (gcc 8.3)
created:
3 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!