Bình luận

• 
  

  0

  

  X  đã bình luận lúc 24, Tháng 8, 2026, 22:48

  Cách giải

  Ta xây dựng một đồ thị vô hướng với m + 2 đỉnh:

  • Đỉnh 0 là vị trí bắt đầu của Tèo.
  • Đỉnh 1 đến m là các cổng dịch chuyển (khi nhập vào cổng dịch chuyển phải có thêm biến id để ghi lại cổng dịch chuyển).
  • Đỉnh m+1 là vị trí nhà của Tèo.

  ---

  Xây dựng đồ thị

  Ta sẽ xây dựng đồ thị với các trường hợp sau:

  1. Trường hợp 1: Tèo tự đi bộ về nhà

     • Ta có cạnh nối từ 0 đến m+1 với trọng số là abs(x-u) + abs(y-v).
     • Nghĩa là ban đầu Tèo đứng ở vị trí (x, y) muốn đi về nhà thì phải đến (u, v), nên Tèo phải đi bộ qua x-u ô và đi xuống y-v ô. Ta dùng hàm abs vì thuật toán Dijkstra chỉ hoạt động trên đồ thị với trọng số dương.

  2. Trường hợp 2: Tèo dùng cổng dịch chuyển

     • Nguyên lý: Cùng hàng hoặc cùng cột là ta sẽ dùng được cổng dịch chuyển.
     • Ta sẽ tạo ra những đường đi từ vị trí ban đầu của Tèo đến từng cổng dịch chuyển. Vì chỉ cần cùng hàng hoặc cùng cột thì sẽ có thể dịch chuyển đến cổng => Trọng số để Tèo đi đến cổng dịch chuyển là min(abs(x-x1), abs(y-y1)) với (x1, y1) là tọa độ cổng.
     • Lý do ta lấy min là vì chỉ cần cùng cột hoặc hàng là ta sẽ dịch chuyển được (mà thời gian dịch chuyển là 0), nên ta sẽ tính xem cần đi bao nhiêu ô để đến được điểm dịch chuyển đó.

  Khi Tèo đã đến cổng dịch chuyển, ta sẽ có 2 hướng đi tiếp:

  • Hướng 1: Từ cổng dịch chuyển, Tèo đi bộ về nhà.

    • Ta sẽ nối từng cổng dịch chuyển với nhà của Tèo (đỉnh m+1), trọng số là abs(x-x1) + abs(y-y1).

  • Hướng 2: Tèo dịch chuyển tới cổng tiếp theo.

    • Đặc điểm của cổng dịch chuyển là cùng hàng hoặc cùng cột là dịch chuyển được nên ta sẽ tính ra 2 trường hợp con:
    • Cùng hàng: Ta sẽ sort x tăng dần từ bé đến lớn.
      • Giả sử trong input mẫu: cổng đầu (2, 2), cổng hai (3, 1), cổng ba (4, 4).
      • Từ cổng 1 đi đến cổng 3 đi theo hàng là tốn abs(x1-x3) = 2.
      • Từ cổng 1 đến cổng 2 tốn abs(x1-x2) = 1.
      • Từ cổng 2 đến cổng 3 tốn abs(x2-x3) = 1.
      • => Khoảng cách cổng 1-3 = cổng 1-2 + cổng 2-3.
      • => Các cổng dịch chuyển sẽ được nối từ cổng có id sang id+1 với trọng số là abs(x1-x2).
    • Cùng cột: Logic tương tự, ta sort theo y và nối các điểm kề nhau.

  ---

  Khi đã xây dựng xong đồ thị, ta chỉ cần chạy hàm Dijkstra với đỉnh ban đầu là 0 để tìm đường đi ngắn nhất đến đỉnh m+1.

  Code mẫu

  #include<bits/stdc++.h>
  
  using namespace std;
  typedef long long ll;
  const int maxn=1e5+50;
  
  ll n,m,x,y,u,v;
  
  struct edge
  {
      ll u;
      ll w;
  };
  struct mr
  {
      ll x;
      ll y;
      ll id;
  };vector<mr>mrr;
  void input()
  {
      cin>>n>>m;
      cin>>x>>y>>u>>v;
      for(int i=1; i<=m;++i){
          ll xx,xy; cin>>xx>>xy;
          mrr.push_back({xx,xy,i});
      }
  }
  vector<edge>adj[maxn];
  bool cmpx(mr a, mr b)
  {
      return a.x<b.x;
  }
  bool cmpy(mr a, mr b)
  {
      return a.y<b.y;
  }
  void kegrp()
  {
      for(auto it:mrr){
          ll a = abs(x-it.x);
          ll b = abs(y-it.y);
          adj[0].push_back({it.id,min(a,b)});
      }
      sort(mrr.begin(),mrr.end(),cmpx);
      for(int i=0; i<m-1; ++i){
          ll wei=abs(mrr[i].x-mrr[i+1].x);
          adj[mrr[i].id].push_back({mrr[i+1].id,wei});
          adj[mrr[i+1].id].push_back({mrr[i].id,wei});
      }
      sort(mrr.begin(),mrr.end(),cmpy);
      for(int i=0; i<m-1; ++i){
          ll wei=abs(mrr[i].y-mrr[i+1].y);
          adj[mrr[i].id].push_back({mrr[i+1].id,wei});
          adj[mrr[i+1].id].push_back({mrr[i].id,wei});
      }
      ll weiend=abs(x-u)+abs(y-v);
      adj[0].push_back({m+1,weiend});
      for(auto it : mrr){
          ll wei=abs(it.x-u)+abs(it.y-v);
          adj[it.id].push_back({m+1,wei});
      }
  }
  ll dist[maxn];
  const long long INF=1e18;
  #define pli pair<ll,ll>
  void dijkstra(ll s)
  {
      for(int i=0; i<=m+2; ++i) dist[i]=INF;
      dist[s]=0;
      priority_queue<pli,vector<pli>,greater<pli>>pq;
      pq.push({0,s});
      while(!pq.empty()){
          ll d = pq.top().first;
          ll u = pq.top().second;
          pq.pop();
          if(d>dist[u]) continue;
          for(auto edg : adj[u]){
              ll v = edg.u;
              ll w = edg.w;
  
              if(dist[u]+w<dist[v]){
                  dist[v]=dist[u]+w;
                  pq.push({dist[v],v});
              }
          }
      }
  }
  void solve()
  {
      kegrp();
      dijkstra(0);
      cout<<dist[m+1];
  }
  int main()
  {
      ios_base::sync_with_stdio(0);cin.tie(nullptr);
      input();
      solve();
      return 0;
  }