POJ 2240 【这题貌似可以直接FLOYD 屌丝用SPFA通过枚举找正权值环 顺便学了下map】

题意：

给了n种硬币的名称，给了m种硬币间的转换关系。

从任意兑换地点开始兑换，看是否能够通过兑换的方式增加金钱。

思路：

用SPFA不断对各个点进行松弛操作，寻找正权值的环。如果找到则输出Yes。

这题测试的时候竟然发现dis数组写成int型...

#include<stdio.h>

#include<map>

#include<string.h>

#include<string>

#include<iostream>

#include<queue>

using namespace std;

int n,m;

int ednum;

bool ok;

bool vis[];

int cnt[];

double dis[];

map<string,int>mymap;

struct edge

{

    int id;

    double plu;

    edge *next;

};

edge edges[];

edge *adj[];

inline void addEdge(int a,int b,double c)

{

    edge *tmp;

    tmp=&edges[ednum];

    ednum++;

    tmp->id=b;

    tmp->plu=c;

    tmp->next=adj[a];

    adj[a]=tmp;

}

bool SPFA(int pos)

{

    int id;

    memset(cnt,,sizeof(cnt));

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

    {

        dis[i]=-;

    }

    memset(vis,,sizeof(vis));

    dis[pos]=;

    queue<int>q;

    q.push(pos);

    vis[pos]=;

    cnt[pos]++;

    while(!q.empty())

    {

        id=q.front();

        q.pop();

        vis[id]=;

        for(edge *p=adj[id];p;p=p->next)

        {

            if(dis[id]*p->plu>dis[p->id])

            {

                cnt[p->id]++;

                if(cnt[p->id]>n)

                    return ;

                dis[p->id]=dis[id]*p->plu;

                if(!vis[p->id])

                {

                    vis[p->id]=;

                    q.push(p->id);

                }

            }

        }

    }

    return ;

}

int main()

{

    string tmp,tmpa,tmpb;

    double num;

    int cas=;

    cin>>n;

    while(n)

    {

        cas++;

        ok=;

        ednum=;

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

        {

            adj[i]=NULL;

        }

        mymap.clear();

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

        {

            cin>>tmp;

            mymap.insert(make_pair(tmp,i));

        }

        cin>>m;

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

        {

            cin>>tmpa>>num>>tmpb;

            addEdge(mymap[tmpa],mymap[tmpb],num);

        }

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

        {

            if(SPFA(i))

            {

                ok=;

                break;

            }

        }

        printf("Case %d: ",cas);

        if(ok)

            printf("Yes\n");

        else

            printf("No\n");

        cin>>n;

    }

}