题意是是否存在一个从自己出发再回到自己且值大于一的环 ， 用Floyd 即可。
can you hear me ?
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<queue>
#include<map>
#include<set>
using namespace std;#define INF 0x3f3f3f3f
double g[50][50] ;
map<string , int > pq ;
int n ;
bool floyd (){for( int k = 0 ; k < n ; k ++ ){for( int i = 0 ; i < n ; i ++ )for(int j = 0 ; j < n ; j ++ ){if( !g[i][k] || !g[k][j]) continue ;g[i][j] = max ( g[i][j] , g[i][k]*g[k][j] ) ;}}for(int i = 0 ; i < n ; i ++ )if(g[i][i] > 1 ) return true ;return false ;
}
int main( ){int m , a , b , c , kase;kase = 1 ;while ( ~scanf("%d" , &n ) && n ){int tran = 0 ;string read , read2 ; double kk ;for(int i = 0 ; i < n ; i ++ ) {cin >> read ;pq[read] = tran ++ ;}scanf("%d" , &m) ;//for( int i = 1 ; i <= n ; i ++ ) g[i].clear() ;//edges.clear() ; ///memset( g , 0 , sizeof( g )) ;for( int i = 0 ; i < m ; i ++ ){cin >> read >> kk >> read2 ;int a = pq[read] , b = pq[read2] ;g[a][b] = kk ;}if( floyd() ) printf("Case %d: Yes\n" , kase ++ ) ;elseprintf("Case %d: No\n" , kase ++ ) ;}return 0 ;
}