又是一道求正权环的水题，不要用c++输入，会超时。
总结一下：求正权环时dist数组初始化为0，源点初始化为题目给出的值，若没有，则dist[1]=1;
求负权环时，dist输出初始化为无穷大，dist[1]=0。
// // main.cpp // Richard // // Created by 邵金杰 on 16/8/12. // Copyright © 2016年 邵金杰. All rights reserved. // #include<iostream> #include<cstdio> #include<vector> #include<cstring> using namespace std; const int maxn=10000+100; struct edge{ int s,e; double r; edge(int s,int e,double r): s(s),e(e),r(r) {} }; vector<edge> edges; double dist[maxn]; int n,m; void input() { char str[maxn][200],str1[200],str2[200]; for(int i=1;i<=n;i++) { scanf("%s",str[i]); } scanf("%d",&m); for(int i=0;i<m;i++) { double r; scanf("%s %lf %s",str1,&r,str2); int s=0,e=0; for(int j=1;j<=n;j++) if(strcmp(str[j],str1)==0) {s=j;break;} for(int j=1;j<=n;j++) if(strcmp(str[j],str2)==0) {e=j;break;} edges.push_back(edge(s,e,r)); } // for(int i=0;i<edges.size();i++) // { // cout<<edges[i].s<<" "<<edges[i].r<<" "<<edges[i].e<<endl; // } } bool Bellman_Ford() { memset(dist,0,sizeof(dist)); dist[1]=1; for(int k=1;k<=n;k++) { for(int i=0;i<edges.size();i++) { int s=edges[i].s; int e=edges[i].e; double r=edges[i].r; if(dist[s]*r>dist[e]) dist[e]=dist[s]*r; } } for(int i=0;i<edges.size();i++) { int s=edges[i].s; int e=edges[i].e; double r=edges[i].r; if(dist[s]*r>dist[e]) return true; } return false; } int main() { int kase=0; while(scanf("%d",&n)&&n) { edges.clear(); input(); printf("Case %d: ",++kase); if(Bellman_Ford()) printf("Yes\n"); else printf("No\n"); } }