rt,这道题我使用了1e18作为INF值,但是我没有开long long,为什么AC了?
code:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N=100005;
struct Node{
int x,y;
int id;
}a[N];
vector<Node> v[N];
int vis[N];
int mi_x,ma_x,mi_y,ma_y,ans=1e18;//这里ans=1e18会爆int
void dfs(int u){
for(int i=0;i<v[u].size();i++){
if(!vis[v[u][i].id]){
vis[v[u][i].id]=1;
mi_x=min(mi_x,a[v[u][i].id].x);
ma_x=max(ma_x,a[v[u][i].id].x);
mi_y=min(mi_y,a[v[u][i].id].y);
ma_y=max(ma_y,a[v[u][i].id].y);
dfs(v[u][i].id);
}
}
}
int main() {
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
a[i].id=i;
}
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
v[x].push_back(a[y]);
v[y].push_back(a[x]);
}
for(int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=1;
mi_x=a[i].x;
ma_x=a[i].x;
mi_y=a[i].y;
ma_y=a[i].y;
dfs(i);
ans=min((ma_x-mi_x+ma_y-mi_y)*2,ans);
}
}
cout<<ans<<endl;
return 0;
}