HDU - 1217 Arbitrage [最短路]

题目大意，货币之间对兑换，如果起始有 1 美元，1美元=0.5英镑 1英镑=10法郎，1法郎=0.21 美元。经过交换 能够得到 1*0.5*10*0.21=1.05 美元，问给定货币和汇率，能够实现上述操作

分析：我们把乘法两边取对数，就变成 lg0.5+lg10+lg0.21>lg 1=0的情况，如果我们给每个参数都取上负数的话，就变成了最短路问是否存在负环

#include <bits/stdc++.h>
#define cl(arr) memset(arr,0,sizeof(arr))
#define fl(arr,val) memset(arr,val,sizeof(arr))
using namespace std;
const int maxn=1e5+50;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
typedef pair<int,int>PII;
typedef long long ll;
map <string,int>mp;
int n;
struct edge
{
    int to;
    double cost;
    edge(int v,double w):to(v),cost(w){}
};
vector<edge>E[maxn];
void addedge(int u,int v,double c)
{
    E[u].push_back(edge(v,c));
}
double d[100];
int cnt[maxn];
bool dijkstra()
{
    for(int i=0;i<100;i++)
    {
        d[i]=1e18;
    }
    priority_queue<PII,vector<PII>,greater<PII> >q;
    d[1]=0;
    q.push(PII(0,1));
    cnt[1]++;
    while(!q.empty())
    {
        PII x=q.top();
        q.pop();
        double cost=x.first;
        int u=x.second;
        for(int i=0;i<E[u].size();i++)
        {
            int v=E[u][i].to;
            double w=E[u][i].cost;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                q.push(PII(d[v],v));
                cnt[v]++;
            }
            if(cnt[v]>n)return true;

        }
    }
    return false;
}
int main()
{
    int Case=1;
    int p=0;
    while(~scanf("%d",&n)&&n)
    {
        for(int i=1;i<105;i++)
        {
            E[i].clear();
        }
        cl(cnt);
        mp.clear();
        int index=0;
        for(int i=1;i<=n;i++)
        {
            string s;
            cin>>s;
            mp[s]=++index;
        }
        int m;
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            string a,b;
            double t;
            cin>>a>>t>>b;
            int u=mp[a];
            int v=mp[b];
            t= -log10(t);
            addedge(u,v,t);
        }
        if(dijkstra())
        {
            printf("Case %d: Yes\n",++p);
        }
        else
        {
            printf("Case %d: No\n",++p);
        }
    }
    return 0;
}