/* 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 ;
}
分享到:
相关推荐
最短路模板 by 程序猿小周 时间复杂度:O(n^3) 适用于:求单源最短路
最短路的Floyd算法PPT课件.pptx
算法上机代码 包含Bellman-Floyd、 Kruskal 、Prim算法、单源最短路算法(Dijkstra)、多段图算法、多源最短路(Floyd)、改进的作业排序
图论- 最短路- Floyd 算法.rar
最短路的Floyd算法PPT学习教案.pptx
floyd算法matlab 利用 MATLAB 实现 Floyd 算法,可对输入的邻接距离矩阵计算图中任意两点间的...优点是容易理解,可以算出任意两个节点之间最短距离的算法,且程序容易实现,缺点是复杂度达到,不适合计算大量数据。
floyd最短路算法 最短路程序
做ACM最短路问题普遍算法的Floyd-Dijkstra-Spfa板子..
最短路问题的Floyd算法与MATLAB程序实现.pdf
本系统采用Dev C++开发平台来进行编写和测试,用到了类、数组、函数,指针、文件的读取存储操作以及DFS算法和所有顶点对的最短路径(Floyd算法)、 图的各种遍历算法等 用无向网表示XX大学的校园景点平面图,图中顶点...
MATLAB 实现floyd最短路算法,
在计算有环有方向的最短路时,可以用Floyd算法计算出任意两点之间的最短路!
【资源说明】 该项目代码主要针对计算机、自动化等相关专业的学生从业者下载使用,项目代码都经过严格调试,确保可以运行!放心下载使用。 也可作为期末课程设计、课程大作业、毕业设计等。具有较高的学习借鉴价值!...
Floyd最短路算法的MATLAB程序,数学建模的使用
代码直接就能用,比较简单的算法实现
用编好的Floyd程序求最短路径,只要画出点和路线,就可以自动计算出最短路径
Floyd最短路matlab算法,经典的运筹学问题。hiuhoojjljljpiojupo