有点想要敲自己一顿了，这道题属于图论当中的比较简单的最短路径，实在是有点汗颜，本来觉得自己思路也是基本上理解了的，看了自己那本图论的算法设计的教材之后，感觉还是蛮好的。
但是现在一做题目竟然wa了 这么多边。。。
呜呜呜~~~
不过幸好是最后这一刻还是来了。。。
因为对于这个题目当中的图而言是乘法所以就相当于说是给图加上了负权值的边，所以我们只要用Floyd算法
有兴趣的话可以去看一下这位大哥写的东西。
http://www.cnblogs.com/twjcnblog/archive/2011/09/07/2170306.html
具体代码如下：
View Code 1 #include<iostream> 2 #define max(a,b) a>b?a:b 3 using namespace std; 4 int main() 5 { 6 char cur[31][31],s[31],e[31]; 7 double temp[31][31],w; 8 int n,t=0,type; 9 while(scanf("%d",&n)!=EOF&&n) 10 { 11 for(int i=0;i<n;i++) 12 { 13 getchar(); 14 scanf("%s",cur[i]); 15 for(int j=0;j<n;j++) 16 { 17 if(i==j)temp[i][j]=1.0; 18 else 19 temp[i][j]=0.0; 20 } 21 } 22 scanf("%d",&type); 23 for(int i=0;i<type;i++) 24 { 25 getchar(); 26 scanf("%s",s); 27 int j,k; 28 for(j=0;j<n;j++)if(strcmp(s,cur[j])==0)break; 29 scanf("%lf",&w); 30 getchar(); 31 scanf("%s",e); 32 for(k=0;k<n;k++)if(strcmp(e,cur[k])==0)break; 33 temp[j][k]=w; 34 } 35 for(int i=0;i<n;i++) 36 { 37 for(int j=0;j<n;j++) 38 { 39 for(int k=0;k<n;k++) 40 { 41 temp[j][k]=max(temp[j][k],temp[j][i]*temp[i][k]); 42 } 43 } 44 } 45 if(temp[0][0]>1)printf("Case %d: Yes\n",++t); 46 else 47 printf("Case %d: No\n",++t); 48 } 49 return 0; 50 }
转载于:https://www.cnblogs.com/nuoyan2010/archive/2012/09/01/2667113.html
