poj2240

一个关于套利的题，就是判断是否有正环，我这里是用的SPFA,只要判断出来一种货币初始为1，最后变得大于1就代表是正环，要注意一下最后对vector的清空，当时从1开始清空，导致wa了两次，找了半天，尽量不要出现小的错误还是很致命的

#include <iostream>

#include<string.h>

#include <cstdio>

#include <queue>

#include <vector>

using namespace std;

#define MAX  99999999;

double dis[+];

double vis[+];

int time[+];

int n;

char name[][];

double fir;

typedef struct

{

    int x;

    double rate;

    //double cost;

}point;

int judge_name( char* str)

{

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

    {

        if(strcmp(str,name[i])==)

            return i;

    }

}

vector<point> p[];

int Spfa(int start)

{

    queue<int> Q;

    memset(time,,sizeof(time));

    memset(vis, , sizeof(vis));

    memset(dis, , sizeof(dis));

    dis[start] = 1.0;

    vis[start] = true;

    time[start]++;

    Q.push(start);

    while (!Q.empty()){

        int temp = Q.front();

        Q.pop();

         vis[temp] = false;

        for(int i=; i<p[temp].size(); i++)

        {

            int v=p[temp][i].x;

            double w=p[temp][i].rate;

            if (dis[v] <dis[temp]*w)

            {

                dis[v] = dis[temp]*w;

                if(dis[start]>1.0)

                {

                //    cout<<start<<endl;

               //     cout<<dis[start]<<endl;;

                    return true;

                }

                if (!vis[v])

                {

                    Q.push(v);

                    vis[v] = true;

                              }

            }

        }

    }

    return false;

}

int main()

{

    int m,s;

    int total=;

    while(cin>>n,n)

    {

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

            cin>>name[i];

        int m;

        cin>>m;

        char str1[],str2[];

        double f;

        point node;

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

        {

            cin>>str1>>f>>str2;

            node.x=judge_name(str2);

            node.rate=f;

            p[judge_name(str1)].push_back(node);

        }

       int flag=;

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

       {

           if(Spfa(i))

           {

               flag=true;

               break;

           }

       }

       if(flag)

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

       else

       printf("Case %d: No\n",++total);

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

        p[i].clear();

    }

    return ;

}