poj2253 解题报告
题意:Freddy Frog暗恋Fiona Frog，在他们之间有n快石头，告诉你这n快石头的坐标，第一快为Freddy Frog的坐标，第n块为Finoa Frog的坐标，Freddy可以借助石头经过任何路径到达Fiona那里，问他最小的弹跳距离是多少
题解:用最短路dij做,额,这样说不准确,也可以用最小生成树的prim做,==!这两个本来就是一种思想,只不过松弛方法不一样,其实还可以floyed做,,,针对这道题都要改一下松弛条件,,dis[i]表示i到原点的路径中的极小最大值,,然后松弛条件if ( dis[j] > max ( dis[x] , map[x][j] ) && v[j] == 0 ) dis[j] = max ( dis[x] , map[x][j] ) ;这样就好了,,我居然sb地不仔细看题,先直接输出答案,没有格式错了一次,后来居然只保留两位小数错了一次,,我已经脑残了,没救了
代码:
#include <iostream>#include <cstring>#include <cstdio>#include <cmath>using namespace std ;const int MAXN = 405 ;double INF = 999999999.0 ;struct Point{ int x , y ;} point[MAXN] ;int n ;double map[MAXN][MAXN] , dis[MAXN] ;double dij() ;int main(){ int i , j , k , Count = 0 ; while( scanf( "%d" , & n ) && n ) { Count ++ ; memset( map , 0 , sizeof( map ) ) ; for( i = 0 ; i < n ; i ++ ) scanf( "%d%d" , & point[i].x , & point[i].y ) ; for( i = 0 ; i < n ; i ++ ) for( j = 0 ; j < n ; j ++ ) { if( i == j ) continue ; map[i][j] = sqrt( double ( ( point[i].x - point[j].x ) * ( point[i].x - point[j].x ) + ( point[i].y - point[j].y ) * ( point[i].y - point[j].y ) ) ) ; } dij() ; printf( "Scenario #%d\nFrog Distance = %.3f\n\n" , Count , dis[1] ) ; } return 0 ;}double dij(){int i , j , x ;bool v[MAXN] ;double m = INF ;memset( v , 0 , sizeof( v ) ) ;for ( i = 0 ; i < n ; i ++ ) dis[i] = INF ;dis[0] = 0 ;for ( i = 0 ; i < n ; i ++ ){m = INF ;x = 0 ;for ( j = 0 ; j < n ; j ++ ){if ( dis[j] < m && v[j] == 0 ){m = dis[j] ;x = j ;}}v[x] = 1 ;for ( j = 0 ; j < n ; j ++ ){if ( dis[j] > max ( dis[x] , map[x][j] ) && v[j] == 0 ) dis[j] = max ( dis[x] , map[x][j] ) ;}}return m ;}