【最短路+floyd】杭电 hdu 1217 Arbitrage

 

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

	URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1217
	Name  : 1217 Arbitrage

	Date  : Sunday, January 15, 2012
	Time Stage : one hour

	Result: 
5259080	2012-01-15 09:36:07	Accepted	1217
203MS	8104K	1697 B
C++	pyy


Test Data :

Review :

本来是想用dijkstra来做的，可是弄了几个小时一直A不了，只好用floyd水过了……
再次接触floyd，发现跟dijkstra不同的点，floyd用的是二维数组，而且进行比较和更新
所用的数组必须是同一个。

真心求dijkstra解法！
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>
#include <map>
#include <string>
#include <iostream>

using namespace std ;

#define min(x, y)	((x) < (y) ? (x) : (y))
#define max(x, y)	((x) > (y) ? (x) : (y))

#define INF		0x0f0f0f0f
#define MAXN	1002

bool	flag ;

int		n, m ;
double	dist[MAXN][MAXN] ;

void floyd ()
{
	int i, j, k ;

	for (k = 1 ; k <= n ; ++k)
	{
		for (i = 1 ; i <= n ; ++i)
		{
			for (j = 1 ; j <= n ; ++j)
			{
				dist[i][j] = max (dist[i][k] * dist[k][j], dist[i][j]) ;
//				printf ("dist[%d][%d] = %lf ; ", i, j, dist[i][j]) ;
				if (i == j && dist[i][j] > 1)
				{
					flag = true ;
					return ;
				}
			}
		}
	}
}

int main ()
{
	int i, j ;
	int s, e ;
	int tcase ;

	tcase = 0 ;
	while (scanf ("%d", &n), n)
	{
		map<string, int> id ;
		string str, str2 ;
		double d ;

		memset (dist, 0, sizeof (dist)) ;
		for (i = 1 ; i <= n ; ++i)
			dist[i][i] = 1 ;

		for (i = 1 ; i <= n ; ++i)
		{
			cin >> str ;
			id[str] = i ;
		}
		scanf ("%d", &m) ;
		for (i = 1 ; i <= m ; ++i)
		{
			cin >> str >> d >> str2 ;
			s = id[str] ;
			e = id[str2] ;
			dist[s][e] = d ;
//			printf ("dist[%d][%d] = %lf; \n", s, e, dist[s][e]) ;
		}
		flag = false ;
		floyd () ;
		++tcase ;
		printf ("Case %d: %s\n", tcase, (flag ? "Yes" : "No")) ;
	}
	return 0 ;
}