uva_road_construction.cpp

#include<bits/stdc++.h>

using namespace std ;

#define M 1000
#define pii pair<int , int >
#define mp make_pair
#define pf printf
#define sf scanf
#define sf1(a ) scanf("%d",&a)
#define pb push_back
#define sf2(a, b) scanf("%d%d",&a ,&b)
#define rep(i,n) for(i = 1 ; i<= n ;i++ )
#define sq(x)  x*x
const double mx = 1000000000;
struct _cv{
double cost ,len ;
int x, y ;

};

struct _node{
int x, y ;

};

vector<_cv > cv;
vector<_node > node;

bool comp(_cv p , _cv q){
  if(!(p.cost - q.cost <= .0000001 && q.cost - p.cost <= .0000001))
    return p.cost > q.cost ;

  else if((p.len  - q.len  <= .0000001 && q.len - p.len <= .0000001))
    return p.len < q.len ;
  else if(p.x != q.x) return p.x < q.x ;
  else return p.y < q.y;

}

map<pii , int> mm;
map<pii , int> track ;
double arr[M][M];

void warshall(int num ){
int i  , j , k;
  rep(k , num ) rep(i , num ) rep(j ,num ){
    if(arr[i][k] + arr[j][k] < arr[i][j])
      arr[i][j] = arr[i][k] + arr[j][k];

  }

return ;
}



int main(){
//   freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);

  int i, j,k , n ,m;
  while(scanf("%d%d",&n ,&m)){
    if(n== 0 && m ==0) break ;
    //m.clear();
    _node var; node.pb(var);
    int num ; num =  n ;
    rep(i, M-1  )rep(j , M -1) arr[i][j] =  mx;
    while( n--){
        _node var;
        double u , v ;
        scanf("%lf%lf",&u , &v );
        var.x = u ;
        var.y = v ;

        node.pb(var );

    }

    while(m--){
        double  rc ;
        int u,v  ;
        scanf("%d%d",&u , &v);
        mm[make_pair(u,v)] =1 ;
        mm[mp(v, u )]=1 ;

        rc = (double)sqrt(sq(node[u].x - node[v].x ) + sq(node[u].y - node[v].y) );

    arr[u][v] =  arr[v][u] = rc ;
    }
    rep(i ,M-1 ) arr[i][i] =  0;
    warshall(num);

    rep(i , num ){
      for(j =  i+1 ;j <= num ;j++){
        _cv var ;
        if(mm.find(mp(i,j ))== mm.end()){
            double _cost ;
            _cost = (double )sqrt(sq(node[i].x- node[j].x) +sq(node[i].y - node[j].y ));
            var.len = _cost ;
            var.cost = arr[i][j] - _cost ;
            var.x = i ;
            var.y = j ;
            cv.pb(var);
           }
        }
      }
    // end of n2

sort(cv.begin() , cv.end() , comp);
    if(cv[0].cost <= 1.0)
      pf("No road required\n");
    else pf("%d %d\n", cv[0].x,cv[0].y  );

  }


return 0 ;
}