[UVa]534:Frogger

此題是最短路徑問題，
可以利用dijkstra法來解決。

[C](0.012)

	#include<stdio.h>
	#include<math.h>
	double min( double a, double b )
	{
	return ( a < b )? a : b;
	}
	double distance( double ax, double ay, double bx, double by )
	{
	return sqrt( ((ax-bx)*(ax-bx)) + ((ay-by)*(ay-by)) );
	}
	int main()
	{
	int n;
	int sets = 1;
	while( scanf( "%d", &n ) != EOF && n != 0 )
	{
	int i;
	double stone[205][5] = {0};
	for( i = 0 ; i < n ; i++ )
	scanf( "%lf%lf", &stone[i][0], &stone[i][1] );
	int now = 0;
	double dijkstra[205][5] = {0};
	for( i = 0 ; i < 205 ; i++ )
	dijkstra[i][0] = 2147483647;
	dijkstra[0][1] = 1;
	double maxdistance = 0;
	int temp = 1;
	while( now != 1 )
	{
	temp = 1;
	for( i = 0 ; i < n ; i++ )
	if( dijkstra[i][1] == 0 )
	{
	dijkstra[i][0] = min( distance(stone[now][0],stone[now][1],stone[i][0],stone[i][1] ), dijkstra[i][0] );
	if( dijkstra[i][0] < dijkstra[temp][0] )
	temp = i;
	}
	now = temp;
	maxdistance = ( dijkstra[now][0] > maxdistance )? dijkstra[now][0] : maxdistance;
	dijkstra[now][1] = 1;
	}
	printf( "Scenario #%d\n", sets++ );
	printf( "Frog Distance = %.3lf\n\n", maxdistance );
	}
	return 0;
	}

view raw UVa534.c hosted with ❤ by GitHub