3 USDollar BritishPound FrenchFranc 3 USDollar 0.5 BritishPound BritishPound 10.0 FrenchFranc FrenchFranc 0.21 USDollar 3 USDollar BritishPound FrenchFranc 6 USDollar 0.5 BritishPound USDollar 4.9 FrenchFranc BritishPound 10.0 FrenchFranc BritishPound 1.99 USDollar FrenchFranc 0.09 BritishPound FrenchFranc 0.19 USDollar 0
Case 1: Yes Case 2: No
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int N = 35;
int n, m;
double d[N], Map[N][N];
struct A
{
char name[100];
}a[35];
int Find(char *s)
{
for(int i = 0; i < n; i++)
if(strcmp(a[i].name, s) == 0)
return i;
}
int SPFA(int start)
{
queue<int> q;
bool inq[N];
for(int i = 0; i < n; i++)
d[i] = 0;
memset(inq, 0, sizeof(inq));
while(!q.empty())
q.pop();
d[start] = 1;
inq[start] = 1;
q.push(start);
while(!q.empty())
{
int x = q.front();
q.pop();
inq[x] = false;
for(int i = 0; i < n; i++)
{
if(d[i] < d[x] * Map[x][i])
{
d[i] = d[x] * Map[x][i];
if(d[start] > 1.0)
return 1;
if(!inq[i])
{
inq[i] = true;
q.push(i);
}
}
}
}
return 0;
}
int main()
{
int i, j, cas = 0;
char s1[35], s2[35];
double s;
while(~scanf("%d",&n) && n)
{
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
if(i == j)
Map[i][j] = 1;
else
Map[i][j] = 0;
}
}
for(i = 0; i < n; i++)
scanf("%s",a[i].name);
scanf("%d",&m);
for(i = 0; i < m; i++)
{
scanf("%s%lf%s",s1, &s, s2);
int u = Find(s1), v = Find(s2);
Map[u][v] = s;
}
int flag = 0;
for(i = 0; i < n; i++)
{
if(SPFA(i) == 1)
{
flag = 1;
break;
}
}
printf("Case %d: ",++cas);
printf("%s\n", flag ? "Yes" : "No");
}
return 0;
}hdu 1217 Arbitrage (最短路之SPFA算法)
原文:http://blog.csdn.net/lyhvoyage/article/details/19248927