[World Final 2005][Uva Live Archive] 3270 - Simplified GSM Network

題目網址: http://goo.gl/gIxJeD

題意: 給定B個基地台，C個城市，R條路，每條路包含兩城市，代表兩程式間有路連接，以及Q個問題，使用者的設備會選擇離所在點距離最近的基地台連接，若從一基地台轉移至另一基地台的話需要一次切換，每個問題問從S城市至D城市所需最少切換次數。



解法: 題目很明白的表明要求最少切換次數，也就是最短路徑，而可以詢問Q次，所以應使用Floyd Warshall來求任兩點間的最短路徑，剩下的問題就是如何建圖，對於每條邊，邊的權重即為邊的兩端點A、B從A走至B需要切換的次數，若A、B屬於同一個基地台，那切換次數就是0，若非，則若AB間的間隔已經非常小，表示他們剛好介於兩個基地台間的中垂線上，故切換次數為1，否則以2分法，找出兩端點的中點M，而分別求出A至M的切換次數加上M至B的切換次數。

TAG: Floyd Warshall

注意: 需要精度判斷

程式碼:

	#include <iostream>
	#include <cstring>
	#include <cstdio>
	#include <cmath>
	using namespace std;
	#define N 60
	#define EPS 1e-9
	#define INF 1e8
	#define clr(x,v) memset( x, v, sizeof(x) )
	const int dcmp( const double &x ) { if( x < -EPS ) return -1; return x > EPS; }
	const double ABS( const double &x ) { return (dcmp(x)<0?-x:x); }
	const double sqr( const double &x ) { return x*x; }
	struct Point {
	double x, y;
	Point( double _x = 0, double _y = 0 ): x(_x), y(_y) {}
	const Point operator+( const Point &op ) const { return Point( x+op.x, y+op.y ); }
	const Point operator-( const Point &op ) const { return Point( x-op.x, y-op.y ); }
	const Point operator*( const double &k ) const { return Point( x*k, y*k ); }
	const Point operator/( const double &k ) const { double t=(dcmp(k)?k:1); return Point( x/t, y/t ); }
	const double operator*( const Point &op ) const { return ( x*op.x+y*op.y ); }
	const double operator^( const Point &op ) const { return ( x*op.y-y*op.x ); }
	const bool operator==( const Point &op ) const { return ( !dcmp(x-op.x)&&!dcmp(y-op.y) ); }
	const bool operator!=( const Point &op ) const { return !((*this)==op); }
	};
	const double disSqr( const Point &a, const Point &b = Point() ) { return sqr(a.x-b.x)+sqr(a.y-b.y); }
	const double dis( const Point &a, const Point &b = Point() ) { return sqrt(disSqr(a,b)); }
	int ti = 0;
	int b, c, r, q;
	int edge[N][N];
	int c2c[N][N];
	Point bs[N], city[N];
	const int findWho( const Point &p )
	{
	int i, ret = 1;
	double mindis = dis( p, bs[1] );
	for( i = 2; i <= b; ++i ) if( dcmp( dis(p,bs[i])-mindis ) < 0 ) {
	ret = i;
	mindis = dis(p,bs[i]);
	}
	return ret;
	}
	const int getRoad( const Point &A, const Point &B )
	{
	int fa = findWho(A), fb = findWho(B);
	if( fa == fb ) return 0;
	Point mid = (A+B)/2;
	if( !dcmp( dis(A,B) ) ) return 1;
	return getRoad( A, mid )+getRoad( mid, B );
	}
	void init( void )
	{
	static int i, x, y, j;
	clr( edge, -1 );
	for( i = 1; i <= b; ++i ) scanf( "%lf%lf", &bs[i].x, &bs[i].y );
	for( i = 1; i <= c; ++i ) scanf( "%lf%lf", &city[i].x, &city[i].y );
	for( i = 1; i <= r; ++i ) {
	scanf( "%d%d", &x, &y );
	edge[x][y] = edge[y][x] = getRoad( city[x], city[y] );
	}
	for( i = 1; i <= c; ++i ) for( j = 1; j <= c; ++j ) {
	if( i == j ) c2c[i][j] = 0;
	else if( edge[i][j] >= 0 ) c2c[i][j] = edge[i][j];
	else c2c[i][j] = INF;
	}
	/*
	for( i = 1; i <= c; ++i ) {
	for( int j = 1; j <= c; ++j ) printf( "%d ", edge[i][j] );
	putchar('\n');
	}
	*/
	/*
	for( i = 1; i <= c; ++i ) {
	for( int j = 1; j <= c; ++j ) printf( "%d ", c2c[i][j] );
	putchar('\n');
	}
	*/
	}
	void solve( void )
	{
	static int i, j, k;
	for( k = 1; k <= c; ++k ) for( i = 1; i <= c; ++i ) for( j = 1; j <= c; ++j )
	c2c[i][j] = min( c2c[i][j], c2c[i][k]+c2c[k][j] );
	/*
	for( i = 1; i <= c; ++i ) {
	for( int j = 1; j <= c; ++j ) printf( "%d ", c2c[i][j] );
	putchar('\n');
	}
	*/
	}
	void output( void )
	{
	static int i, x, y;
	printf( "Case %d:\n", ++ti );
	for( i = 1; i <= q; ++i ) {
	scanf( "%d%d", &x, &y );
	if( c2c[x][y] == INF ) puts("Impossible");
	else printf( "%d\n", c2c[x][y] );
	}
	}
	int main( void )
	{
	int i;
	while( scanf( "%d%d%d%d", &b, &c, &r, &q ) == 4 && (b||c||r||q) ) {
	init();
	solve();
	output();
	}
	return 0;
	}

view raw 3270 - Simplified GSM Network.cpp hosted with ❤ by GitHub