题目描述

当套利的机会出现时，你的算法交易系统会自动识别并赚取盈利。你可以交易共n种货币。给定m种外汇交易的汇率规则，第i条规则为，可以用1元ai货币兑换出ri元的bi货币。请识别能否无风险套利？

输入

第一行为正整数n和m，n<=30，m<=500。接着一行为n种货币的英文简写，由空格隔开。接着为m行，每一行是一条汇率信息：ai,ri,bi。汇率都是10000内的浮点数。

输出

输出Yes或No

输入样例

3 3

RMB USD EUR

EUR 1.2 USD

USD 7 RMB

RMB 0.12 EUR

输出样例

Yes

我的代码：

#include<bits/stdc++.h>
using namespace std;
vector<int>to[501]; 
vector<double>w[501];
int n,m,cnt[501];
bool in[501];
double d[501],r;
map<string,int>id;
string x,y;
bool SPFA(){
	queue<int> q;
	for(int i=1;i<=n;i++)q.push(i),in[i]=cnt[i]=1;
	while(!q.empty()){
		int v,u=q.front(); q.pop(); in[u]=0;
		for(int i=1;i<to[u].size();i++)
			if(d[v=to[u][i]]>d[u]+w[u][i]){
				d[v]=d[u]+w[u][i];
				if(!in[v])in[v]=1,cnt[v]++,q.push(v);
				if(cnt[v]>n) return 1;
			}
	}
	return 0;
}
int main(){
	freopen("arbitrage.in","r",stdin);
	freopen("arbitrage.out","w",stdout);
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>x,id[x]=i;
	for(int i=0;i<m;i++){
		cin>>x>>r>>y;
		to[id[x]].push_back(id[y]);
		w[id[x]].push_back(r);
	}
	bool flag=SPFA();
	if(flag==1) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}