HDOJ 1217 Floyed Template

解题思路：
1.map简单应用
2.Floyd算法的变形，之后判断dis[i][i]，如果大于1，则存在利润！

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <cstring>

 #include<map>

 using namespace std;

 map<string,int>name;

 const int INF = ;

 const int MAXSIZE = ;

 const int MAXN = ;

 double g[MAXN][MAXN];

 //dis[][]记录任意两点间的最短路径，初始的dis[][]记录直接路径

 void floyed(double dis[][MAXN],int n){//节点从1~n编号

     int i,j,k;

     for(k = ; k <= n; k++)

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

          for(j = ; j <= n; j++)

              if(dis[i][j] < dis[i][k] * dis[k][j])

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

 }

 int main(){

     int n,i,m,j;

     string str1,str2;

     double r;

     int iCase = ;

     while(scanf("%d",&n),n){

         iCase++;

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

             cin>>str1;

             name[str1] = i;

         }

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

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

                if(i == j) g[i][j] = ;

                else g[i][j] = ;

            }

         scanf("%d",&m);

         while(m--){

             cin>>str1>>r>>str2;

             g[name[str1]][name[str2]] = r;

         }

         floyed(g,n);

         bool flag = false;

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

           if(g[i][i] > ){

             flag = true;

             break;

           }

         }

         if(flag)  printf("Case %d: Yes\n",iCase);

         else printf("Case %d: No\n",iCase);

     }

     return ;

 }