Arbitrage

poj-2240

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cmath>

#include<map>

using namespace std;

map<string,int>ma;

int n;

int m;

float graph[32][32];

float d[32][32];

void floyd(){

    for(int k=0;k<n;k++){

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

            for(int j=0;j<n;j++){

                if(d[i][j]<d[i][k]*d[k][j]){

                    d[i][j]=d[i][k]*d[k][j];

                }

            }

        }

    }

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    int c=0;

    while(cin>>n&&n){

        string s;

        ma.clear();

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

            cin>>s;

            ma[s]=i;

        }

        cin>>m;

        string s1,s2;

        float k;

        memset(d,0,sizeof(d));

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

            cin>>s1>>k>>s2;

            int x=ma[s1];

            int y=ma[s2];

            graph[x][y]=k;

            d[x][y]=k;

        }

        floyd();

        bool flag=false;

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

            if(d[i][i]>1.0){

                flag=true;

                break;

            }

        }

        cout<<"Case "<<++c<<": ";

        if(flag)

            cout<<"Yes"<<endl;

        else cout<<"No"<<endl;

    }

    return 0;

}
巴特西

POJ-2240(floyd算法简单应用）

Arbitrage

poj-2240

最新文章

热门文章
