题目地址：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; }