【最短路+dijkstra+floyd+spfa】1596 find the safest road

Dijkstra 算法

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
    Copyright (c) 2011 panyanyany All rights reserved.

    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1596
    Name  : 1596 find the safest road

    Date  : Sunday, January 22, 2012
    Time Stage : half an hour

    Result: 
5286524	2012-01-22 16:22:38	Accepted	1596
1015MS	6632K	1962 B
C++	pyy


Test Data :

Review :
//----------------------------------------------------------------------------*/

#include <cstdio>
#include <cstring>
#include <cstdlib>

#include <iostream>
#include <string>
#include <queue>

using namespace std ;

#define INF        (-1)
#define MAXN       1002

typedef __int64    LL ;

#define min(x, y)    ((x) < (y) ? (x) : (y))
#define max(x, y)    ((x) > (y) ? (x) : (y))
#define MEM(a, v)    memset (a, v, sizeof (a))

bool	used[MAXN] ;

int		n, q ;
double	map[MAXN][MAXN], dist[MAXN] ;

double dijkstra (const int beg, const int end)
{
	int i, j ;
	int iMinPath ;
	double MaxSafe ;

	MEM (used, 0) ;
	for (i = 1 ; i <= n ; ++i)
		dist[i] = map[beg][i] ;

	for (i = 1 ; i <= n ; ++i)
	{
		iMinPath = 1 ;
		MaxSafe = 0 ;
		for (j = 1 ; j <= n ; ++j)
		{
			if (used[j] || dist[j] == 0)
				continue ;
			if (dist[j] > MaxSafe)
			{
				iMinPath = j ;
				MaxSafe = dist[j] ;
			}
		}
		used[iMinPath] = 1 ;
		for (j = 1 ; j <= n ; ++j)
		{
			if (used[j] || dist[iMinPath] == 0 || map[iMinPath][j] == 0)
				continue ;
			if (dist[j] == 0 || dist[j] < dist[iMinPath] * map[iMinPath][j])
				dist[j] = dist[iMinPath] * map[iMinPath][j] ;
		}
	}
	return dist[end] ;
}

int main ()
{
	int i, j ;
	int x, y ;
	double ret ;
	while (~scanf ("%d", &n))
	{
		for (i = 1 ; i <= n ; ++i)
			for (j = 1 ; j <= n ; ++j)
			{
				scanf ("%lf", &map[i][j]) ;
			}

		scanf ("%d", &q) ;
		for (i = 1 ; i <= q ; ++i)
		{
			scanf ("%d%d", &x, &y) ;
			ret = dijkstra (x, y) ;
			if (ret == 0)
				puts ("What a pity!") ;
			else
				printf ("%.3lf\n", ret) ;
		}
	}
	return 0 ;
}

Floyd 算法

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
    Copyright (c) 2011 panyanyany All rights reserved.

    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1596
    Name  : 1596 find the safest road

    Date  : Sunday, January 22, 2012
    Time Stage : half an hour

    Result: 
5286856	2012-01-22 19:02:13	Accepted	1596
3484MS	6620K	1456 B
C++	pyy


Test Data :

Review :

//----------------------------------------------------------------------------*/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

#include <iostream>
#include <string>
#include <queue>

using namespace std ;

#define INF        (-1)
#define MAXN       1002

typedef __int64    LL ;

#define min(x, y)    ((x) < (y) ? (x) : (y))
#define max(x, y)    ((x) > (y) ? (x) : (y))
#define MEM(a, v)    memset (a, v, sizeof (a))

int		n, q ;
double	map[MAXN][MAXN] ;

void floyd ()
{
	int i, j, k ;
	double d ;
	for (k = 1 ; k <= n ; ++k)
		for (i = 1 ; i <= n ; ++i)
			for (j = 1 ; j <= n ; ++j)
			{
				// 像这种数据这么大的题（n<=1000），加多条判断语句都会超时……
				// 之前这里就是加了一条判断，结果就超时了……无限TLE
				d = map[i][k] * map[k][j] ;
				if (map[i][j] < d)
					map[i][j] = d ;
			}
}

int main ()
{
	int i, j ;
	int x, y ;
	double ret ;

	while (~scanf ("%d", &n))
	{
		for (i = 1 ; i <= n ; ++i)
			for (j = 1 ; j <= n ; ++j)
			{
				scanf ("%lf", &map[i][j]) ;
			}

		floyd () ;
		scanf ("%d", &q) ;
		for (i = 1 ; i <= q ; ++i)
		{
			scanf ("%d%d", &x, &y) ;
			ret = map[x][y] ;
			if (ret == 0)
				puts ("What a pity!") ;
			else
				printf ("%.3lf\n", ret) ;
		}
	}
	return 0 ;
}

Spfa 算法

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
    Copyright (c) 2011 panyanyany All rights reserved.

    URL   : 
    Name  : 

    Date  : 
    Time Stage : 

    Result: 
5287003	2012-01-22 21:15:06	Accepted	1596
1046MS	6656K	1783 B
C++	pyy


Test Data :

Review :

//----------------------------------------------------------------------------*/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

#include <iostream>
#include <string>
#include <queue>

using namespace std ;

#define INF        (-1)
#define MAXN       1002

typedef __int64    LL ;

#define min(x, y)    ((x) < (y) ? (x) : (y))
#define max(x, y)    ((x) > (y) ? (x) : (y))
#define MEM(a, v)    memset (a, v, sizeof (a))

bool	used[MAXN] ;

int		n, q ;
double	map[MAXN][MAXN], dist[MAXN] ;

double spfa (const int beg, const int end)
{
	int i, t ;
	double d ;
	queue<int>	q ;

	MEM (used, 0) ;
	MEM (dist, 0) ;

	q.push (beg) ;
	used[beg] = 1 ;
	dist[beg] = 1 ;	// 记得要初始化出发点为1

	while (!q.empty ())
	{
		t = q.front () ;
		q.pop () ;

		for (i = 1 ; i <= n ; ++i)
		{
			d = dist[t] * map[t][i] ;
			if (dist[i] < d)
			{
				dist[i] = d ;
				if (!used[i])
				{
					q.push (i) ;
					used[i] = 1 ; // 第一次忘了这个，死循环
				}
			}
		}
		used[t] = 0 ;
	}
	return dist[end] ;
}

int main ()
{
	int i, j ;
	int x, y ;
	double ret ;

	while (~scanf ("%d", &n))
	{
		for (i = 1 ; i <= n ; ++i)
			for (j = 1 ; j <= n ; ++j)
			{
				scanf ("%lf", &map[i][j]) ;
			}

		scanf ("%d", &q) ;
		for (i = 1 ; i <= q ; ++i)
		{
			scanf ("%d%d", &x, &y) ;
			ret = spfa (x, y) ;
			if (ret == 0)
				puts ("What a pity!") ;
			else
				printf ("%.3lf\n", ret) ;
		}
	}
	return 0 ;
}