图论——最短路——bellman_ford

1   流程

    dist[所有点] = INF
    dist[起始点] = 0

    for( k条边 )
    {
        复制上一轮情况

        扫描所有出边并更新
    }

    判断是否能走

2   code

    int bell_man( int u )
    {
        memset( dist, 0x3f, sizeof dist );
        dist[u] = 0;

        for( int i = 0; i < k; i ++ )
        {
            memcpy( back, dist , sizeof dist );

            for( int j = 1; j <= m; j ++ )
            {
                int x = a[j], y = b[j], z = c[j];

                dist[y] = min( dist[y] , back[x] + z );
            }
        }

        if( dist[n] >0x3f3f3f3f/2 )
            return -1;
        else
            return dist[n];
    }