http://poj.org/problem?id=2240

深刻体现了自己代码能力有问题外加改模板能力有问题。外加Debug有问题。以后做到：
1、算法原理能够轻易弄出来。

2、代码模板自己收集各种使用方法，以及已经的做过的改变的方法；

3、没有完整清晰的思路不写程序；

4、在Debug时没有基本绝对的把握，不点击“编译+执行”，不乱试

回到这道题：
我主要是想把Bellman-Ford的模板改为链式前向星的，然后就各种悲剧调试......

学到三点：1、比例的初始化，求最大，源1.0，尚不可到达0， 

    2、Bellman-Ford求环，能够将原来的n-1次循环（就是最多经过n-1条边时最短路径），改为n次循环，当然也能够再把判负权的代码改了，相当于第n次。  这就是我以下贴的两个版本号的代码：
   3、链式前向星的Bellman-Ford模板例如以下

两种版本号都是125ms AC--事实上一样

n次循环：

#include<cstdio>

#include<cstring>

#include <string>

#include <map>

#include <iostream>

using namespace std;

//#define INF 0x0f0f0f0f

const double INF = 0;

#define MAXN 1011

#define Max(a,b) (a)>(b)?(a):(b)

struct Node{

   int to;

   double w;

   int next;

}edge[MAXN];

int head[MAXN],s,n,m,path[MAXN];

double dist[MAXN];//注意w以及该数组的类型

using namespace std;

void init()

{

    memset(head,-1,sizeof(head));

    memset(path,-1,sizeof(path));

}

void addEdge(int u,int v,double w,int k)

{

    edge[k].to=v;

    edge[k].w=w;

    edge[k].next=head[u];

    head[u]=k;/*起点为u的边为edge[k]*/

}

int Bellman_Ford(int v0)//v0--soure

{

    for(int i=0;i<n;i++)dist[i]=0;//1.0;

    dist[v0]=1.0;

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

        for(int u=0;u<n;u++)

        {

            for(int j=head[u];j!=-1;j=edge[j].next)

            {

                if(dist[u]*edge[j].w>dist[edge[j].to])

                {

                        dist[edge[j].to]= dist[u]*edge[j].w;

                        path[edge[j].to]=u;

                }

            }

        }

    if(dist[v0]>1.0)return 1;

    return 0;

}

int main()

{

   // freopen("poj2240.txt","r",stdin);

    int icase=0,flag;

    double w;

    string u,v;

    string str;

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

    {

        init();

        map<string, int>ss;

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

        {

            cin>>str;

            ss[str]=i;

        }

        scanf("%d",&m);

        for(int i=0;i<m;i++)

        {

            cin >> u >> w >> v;

            addEdge(ss[u],ss[v],w,i);

        }

        flag=1;

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

        {

            if(Bellman_Ford(i)){flag=0;printf("Case %d: Yes\n",++icase);break;}

        }

        if(flag) printf("Case %d: No\n",++icase);

    }

    return 0;

}

改负权代码  能够作为链式前向星的Bellman-Ford的模板：

#include<cstdio>

#include<cstring>

#include <string>

#include <map>

#include <iostream>

using namespace std;

//#define INF 0x0f0f0f0f

const double INF = 0;

#define MAXN 1011

#define Max(a,b) (a)>(b)?(a):(b)

struct Node{

   int to;

   double w;

   int next;

}edge[MAXN];

int head[MAXN],s,n,m,path[MAXN];

double dist[MAXN];//注意w以及该数组的类型

using namespace std;

void init()

{

    memset(head,-1,sizeof(head));

    memset(path,-1,sizeof(path));

}

void addEdge(int u,int v,double w,int k)

{

    edge[k].to=v;

    edge[k].w=w;

    edge[k].next=head[u];

    head[u]=k;/*起点为u的边为edge[k]*/

}

int Bellman_Ford(int v0)//v0--soure

{

    for(int i=0;i<n;i++)dist[i]=0;//1.0;

    dist[v0]=1;

    int i,j,l,u,k;

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

        for(u=0;u<n;u++)

        {

            for(j=head[u];j!=-1;j=edge[j].next)

            {

                if(dist[u]*edge[j].w>dist[edge[j].to])

                {

                        dist[edge[j].to]= dist[u]*edge[j].w;

                        path[edge[j].to]=u;

                }

            }

        }

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

    {

        for(k=head[j];k!=-1;k=edge[k].next)

        {

            if(edge[k].to == v0 && dist[j]*edge[k].w>1.0)//dist[edge[k].to])

                return 1;

        }

    }

    return 0;

}

int main()

{

    //freopen("poj2240.txt","r",stdin);

    int icase=0,flag;

    double w;

    string u,v;

    string str;

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

    {

        init();

        map<string, int>ss;

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

        {

            cin>>str;

            ss[str]=i;

        }

        scanf("%d",&m);

        for(int i=0;i<m;i++)

        {

            cin >> u >> w >> v;

            addEdge(ss[u],ss[v],w,i);

        }

        flag=1;

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

        {

            if(Bellman_Ford(i)){flag=0;printf("Case %d: Yes\n",++icase);break;}

        }

        if(flag) printf("Case %d: No\n",++icase);

    }

    return 0;

}