题目地址：http://poj.org/problem?id=2240
string s; cin>>s 超级慢 TLE ，用scanf %s 就47ms
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
const int INF=(1<<30);
struct Edge{int from,to; double rate;Edge(int f,int t,double r):from(f),to(t),rate(r){}
};
vector<Edge> edges;
map<string,int> ID;
double dist[30+5];
bool Bellman_ford(int s,int n)
{fill(dist,dist+n,0);dist[s]=10;for(int k=1;k<n;k++) //从u~v点经过k条边for(int i=0;i<edges.size();i++){int u=edges[i].from;int v=edges[i].to;double r=edges[i].rate;dist[v]=max(dist[v],dist[u]*r);}if(dist[s]>10.0) return true;for(int i=0;i<edges.size();i++){int u=edges[i].from;int v=edges[i].to;double r=edges[i].rate;if(dist[v]<dist[u]*r) return true;}return false;
}
int main()
{int n,kase=0; double r; char s1[100],s2[100];while(scanf("%d",&n)&&n){ID.clear();string n1,n2;for(int i=0;i<n;i++){scanf("%s",s1);ID[n1=s1]=i;}scanf("%d",&n);edges.clear();for(int i=0;i<n;i++){scanf("%s%lf%s",s1,&r,s2);edges.push_back(Edge(ID[n1=s1],ID[n2=s2],r));}printf("Case %d: %s\n",++kase,Bellman_ford(0,ID.size())?"Yes":"No");}return 0;
}