bellman_ford算法

适用条件： 权值存在负值，

最主要应用于： 限制了边数条件的时候，(如：只经过k条路径，求i -> n的最短距离)。当题目中有边数限制的时候，有没有负环对求最后的答案无影响。

时间复杂度:O( n * m )

struct edg
{
    int a,b,w;
}edgs[N];


int bell_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;

    for(int i = 0 ; i < k ; i++) // 循环k次，最多经过k条边的含义。   源点到某结点经过的路线路径（  <= k条边  ）
    {
        memcpy(backup,dist,sizeof dist); //为什么要用backup将原先的dist复制一遍呢？ 因为在第二个for循环中，dist会发生改变，而每一个dist[]的值，都应该被原先的backup【】值来进行修改。所以适用backup[]。
        for(int j = 0 ; j < m ; j++) //遍历所有的结点
        {
            int start = edgs[j].a;
            int end = edgs[j].b;
            int wei = edgs[j].w;
            dist[end] = min(dist[end] , backup[start] + wei);
        }
    }

    if(dist[n] >= 0x3f3f3f3f / 2)
    {
        return -1; //代表源点到达不了n点。 为什么使用的是0x3f3f3f3f / 2呢？这是因为如果源点到不了n点，但是有可能有其他结点可以到达n点，从而修改了dist[n]的值。  
    }
    else
    {
        return dist[n];
    }
}