LiveArchive 5865 - Finding Bottleneck Shorstet Paths

問題概要

N個のノードがある。各ノードには座標(x,y)がある。ノードuからノードvへのコストは２点間のpathの中の距離pij=(x_i-x_j)²+(y_i+y_j)²の最大値である。srcからdstへのpathのコストを最小化せよ。

制約

• 1 ≤ N ≤ 1000
• 0 ≤ x_i, y_i < 2¹⁵

解法

全てのエッジを列挙してdistを昇順にソートする。
後はUnionfindをしてsrcとdstが繋がるまでループで繋げる作業を繰り返す。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 1010
typedef pair<int,int> pii;
 
struct Edge{
  int u,v,dist;
  Edge(int u,int v,int dist) : u(u),v(v),dist(dist) {}
   
  bool operator < (const Edge &e)const{
    return dist < e.dist;
  }
};
 
int par[MAX],rank[MAX];
 
void init(int N){
  for(int i = 0 ; i < N ; i++){
    par[i] = i;
    rank[i] = 0;
  }
}
 
int find(int x){
  if(par[x] == x){
    return x;
  }
  return par[x] = find(par[x]);
}
 
void unite(int x,int y){
  x = find(x);
  y = find(y);
 
  if(x == y){
    return;
  }
  if(rank[x] < rank[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(rank[x] == rank[y]){
      rank[x]++;
    }
  }
}
 
bool same(int x,int y){
  return find(x) == find(y);
}
 
int getDist(pii a,pii b){
  return pow(a.first-b.first,2.) + pow(a.second-b.second,2.);
}
 
int main(){
  int N;
  while(cin >> N,N){
    vector<pii> vec;
    for(int i = 0 ; i < N ; i++){
      int x,y;
      cin >> x >> y;
      vec.push_back(pii(x,y));
    }
    vector<Edge> es;
    for(int i = 0 ; i < N ; i++){
      for(int j = i+1 ; j < N ; j++){
        es.push_back(Edge(i,j,getDist(vec[i],vec[j])));
      }
    }
    int src,dst;
    cin >> src >> dst; src--; dst--;
    init(N);
    sort(es.begin(),es.end());
    int ans = -1;
    for(int i = 0 ; i < (int)es.size() ; i++){
      Edge e = es[i];
      if(same(src,dst)) break;
      if(!same(e.u,e.v)){
        unite(e.u,e.v);
        ans = e.dist;
      }
    }
    cout << ans << endl;
  }
  return 0;
}