4656172_ole.cpp

部分PKU上的源码

#include<iostream>
#include<string>
#define EPS 1e-8
using namespace std;
string money[35];
string input1,input2;
struct change
{
	int u,v;
	float w;
}e[1000];
float dis[35];
int n,el;
int getmoney(string x)
{
	for(int count=0;count<n;count++)
	{
		if(money[count]==x) return count;
	}
	return -1;
}
void floyd()
{
	int count;
	for(count=0;count<n;count++)
	{
		dis[count]=0.0;
	}
	dis[0]=1;
	int f;
	for(count=0;count<n-1;count++)
	{
		f=1;
		for(int i=0;i<el;i++)
		{
			if(dis[e[i].v]+EPS<dis[e[i].u]*e[i].w+EPS)
			{
				dis[e[i].v]=dis[e[i].u]*e[i].w;
				cout<<dis[e[i].v]<<endl;
				f=0;
			}
		}
		if(f==1)
		{
			if( dis[0]>1.00) cout<<"YES"<<endl;
			else cout<<"NO"<<endl;
			return;
		}
	}
	for(int j=0;j<el;j++)
	{
		if(dis[e[j].v]+EPS<dis[e[j].u]*e[j].w+EPS)
		{
			cout<<"YES"<<endl; return;
		}
	}
	cout<<"NO"<<endl;return ;
}
int main()
{
	int testnumber=0;
	while(cin>>n)
	{
		testnumber++;
		if(n==0) break;
		int count,temp;
		for(count=0;count<n;count++)
		{
			cin>>money[count];
		}
		cin>>temp;
		el=0;
		for(count=0;count<temp;count++)
		{
			float x;
			int a,b;
			cin>>input1>>x>>input2;
			a=getmoney(input1);
			b=getmoney(input2);
			e[el].u=a;
			e[el].v=b;
			e[el++].w=x;
		}
		cout<<"Case "<<testnumber<<": ";
		floyd();
	}
	return 0;
}