POJ 2240 Arbitrage
元の通貨交換のテーマと似ていて、n中通貨とm中通貨の間の交換為替レートをあげて、富を増値させることができるかどうかを聞いています.ここでmapを使いました.Wrongは2回、1回の辺集配列が小さくなって、それからYes、No大文字と小文字が間違っていて、悲しいですね.朝のいい気分に影響します.Bellman-Ford.
コード:
コード:
#include<iostream>
#include<string>
#include<map>
#define maxn 40
using namespace std;
map<string,int> mp;
struct Edge
{
int v,u;
double w;
} e[1005];
int size,n;
double dist[maxn];
void AddEdge(int a,int b,double c)
{
e[size].u=a;
e[size].v=b;
e[size].w=c;
size++;
}
bool Bellman_Ford()
{
int i,j;
for( i=1; i<=n; i++){
bool flag=false;
for( j=0; j<size; j++){
// cout<<e[j].u<<' '<<e[j].w<<endl;
if( dist[e[j].u]*e[j].w>dist[e[j].v]){
dist[e[j].v]=dist[e[j].u]*e[j].w;
flag=true;
}
}
if( !flag) break;
if( i==n&&flag) return true;
}
return false;
}
int main()
{
int m,ca,i;
double c;
string str1,str2;
ca=0;
while( cin>>n&&n){
++ca;
mp.clear();
for( i=1; i<=n; i++){
cin>>str1;
mp[str1]=i;
}
cin>>m;
memset(e,0,sizeof(e));
size=0;
while( m--){
cin>>str1>>c>>str2;
AddEdge(mp[str1],mp[str2],c);
}
memset(dist,0,sizeof(dist));
dist[1]=1;
cout<<"Case "<<ca<<": ";
if( Bellman_Ford())
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}