求助大佬
查看原帖
求助大佬
1159443
wangluochen楼主2024/7/20 16:40

把数据开到最大了,还是RE;

#include<bits/stdc++.h>

using namespace std;
const long long N = 1e5, M = 2e5 + 10;

struct E {
  long long v, w, x;
} e[M * 2];

long long n, m, h[N], cnte,a[N],b[N];

void adde(long long u, long long v, long long w) { e[++cnte] = E{v, w, h[u]}, h[u] = cnte; }

struct S {
  long long u, d;
};

bool operator<(const S &x, const S &y) { return x.d > y.d; }

priority_queue<S> q;
 long long dis[N];
bool vis[N];

 long long res = 0, cnt = 0;

void Prim() {
  memset(dis, 0x3f, sizeof(dis));
  dis[1] = 0;
  q.push({1, 0});
  while (!q.empty()) {
    if (cnt >= n) break;
    long long u = q.top().u, d = q.top().d;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    ++cnt;
    res +=d ;
    for (long long i = h[u]; i; i = e[i].x) {
      long long v = e[i].v, w = e[i].w;
      if (w < dis[v]) {
        dis[v] = w, q.push({v, w});
      }
    }
  }
}

int main() {
  cin >> n ;
  for (long long i = 1; i <= n; ++i) {
    cin >> a[i]>>b[i]; 
  }for(long long i=1;i<=n;i++){
  	for(long long j=i+1;j<=n;j++){
  		  adde(i,j,min(abs(a[i]-a[j]), abs(b[i]-b[j])));
  		  adde(j,i,min(abs(a[i]-a[j]), abs(b[i]-b[j])));
	  }
  }
  
  Prim();

    cout << res;
  
}
  
2024/7/20 16:40
加载中...