#include <stdio.h>#include <iostream>#include <map>#include <string>using namespace std;#define INF 0xfffff#define MAX 1100float dist[MAX], path[MAX][MAX];bool sign[MAX];/* 注意相应权值不能为负，且时间复杂度较高 *//*算法步骤如下： 1. 初始时令 S={V0},T={其余顶点}，T中顶点对应的距离值 若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值 若不存在<V0,Vi>，d(V0,Vi)为∞ 2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S 3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值 重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止*/void initialize(int n) //初始化{ for(int i=1; i<=n; i++) { { //pre[i] = 0; dist[i] = 0; //将距离开始全变为最大 sign[i] = false; } for(int j=1; j<=n; j++) if(i == j) path[i][j] = 1.0; //图初始 else path[i][j] = 0; }}bool dijkstra(int n, int source ){ for(int i=1; i<=n; i++) { dist[i] = path[source][i]; //将与源点有关的点的距离加入dist sign[i] = false; //if(dist[i] == INF) //确定有关系的点的前驱，无则为0 //pre[i] = 0; //else // pre[i] = source; } dist[source] = 1.0; //源点自身长度为0 sign[source] = 1;/* 依次将未放入sign集合的结点中，取dist[]最小值的结点，放入结合sign中 一旦sign包含了所有n中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度*/ for(int i=2; i<=n; i++) { //int min = INF; int current = source; for(int j=1; j<=n; j++) //找出当前未使用点j的dist[j]的最小值 { if( (!sign[j]) && dist[j] * path[current][j] > dist[j] ) {current = j; /*min = dist[j];*/} } sign[current] = true; //表示当前点最短距离已经找到 if( dist[source] > 1.0) return true; for(int j=1; j<=n; j++) //更新当前点到未找到点的距离 //if( (!sign[j]) && path[current][j] < INF) { int newdist = dist[current] * path[current][j]; if(newdist > dist[j] ) {dist[j] = newdist; /*pre[j] = current;*/} } }return false; }/*void search_path(int n, int start, int end){ int road[MAX]; int total = 1; road[total++] = end; //从后向前查找 int current = pre[end]; //路径存在pre中 while( current != start) //递归查找，类似并查集 { road[total++] = current; current = pre[current]; } road[total] = start; //最后的开始点存入 for(int i=total; i>=1; i--) //输出 { if( i!=1) printf("%d ->", road[i]); else printf("%d
", road[i]); }}*/void input(int line){ map<string, int>list; for(int i=1; i<=line; i++) { string temp; cin >> temp; list[temp] = i; } int count; scanf("%d", &count); string a, b; float weight; for(int i=0; i<count; i++) { cin >> a >> weight >> b; //if(path[list[a]][list[b]] > weight) //有多条路，保存最短的那条 { path[list[a]][list[b]] = weight; //path[list[b]][list[a]] = weight; //无向图双向 } }}int main(){ int n, T=0; while(~scanf("%d", &n) && n ) { initialize(n); input(n); int flag =1; for(int i=1; i<=n; i++) { if(dijkstra(n, i) ) {printf("Case %d: Yes
", ++T); flag = 0; break;} } if(flag) {printf("Case %d: No
", ++T); } } return 0; }