poj2240 最短路判环

题意：与poj1680一样，有不同的换钱渠道，可以完成特定两种货币的交换，并且有汇率，只不过此题是单向边，然后问是否能使财富增加

与poj1680一样，建图之后直接spfa判增值的环即可

 #include<iostream>

 #include<cstdio>

 #include<string>

 #include<cstring>

 #include<queue>

 #include<map>

 #include<vector>

 using namespace std;

 int head[],nxt[],point[],size;

 double val[],dist[];

 bool vis[];

 int n,p,t[];

 void add(int a,int b,double v){

     int i;

     for(i=head[a];~i;i=nxt[i]){

         if(point[i]==b){

             if(val[i]<v)val[i]=v;

             return;

         }

     }

     point[size]=b;

     val[size]=v;

     nxt[size]=head[a];

     head[a]=size++;

 }

 void spfa(){

     int i;

     memset(dist,,sizeof(dist));

     memset(vis,,sizeof(vis));

     memset(t,,sizeof(t));

     dist[]=;

     vis[]=;

     queue<int>q;

     q.push();

     bool f=;

     while(!q.empty()&&f){

         int u=q.front();

         q.pop();

         vis[u]=;

         for(i=head[u];~i;i=nxt[i]){

             int j=point[i];

             double v=dist[u]*val[i];

             if(dist[j]<v){

                 dist[j]=v;

                 if(!vis[j]){

                     q.push(j);

                     vis[j]=;

                     t[j]++;

                     if(t[j]>n)f=;

                 }

             }

         }

     }

     if(f)printf("Case %d: No\n",++p);

     else printf("Case %d: Yes\n",++p);

 }

 int main(){

     p=;

     while(scanf("%d",&n)!=EOF&&n!=){

         map<string,int>M;

         int i;

         string tmp;

         memset(head,-,sizeof(head));

         size=;

         for(i=;i<=n;i++){

             cin>>tmp;

             M[tmp]=i;

         }

         int m;

         scanf("%d",&m);

         for(i=;i<=m;i++){

             string t1,t2;

             double a;

             cin>>t1>>a>>t2;

             add(M[t1],M[t2],a);

         }

         spfa();

     }

     return ;

 }