int spfa_bfs(int s)

{

    ///s表示起点。

    queue <int> q;

    memset(d,0x3f,sizeof(d)); ///d数组中存下的就是最短路径（存在的话）

    d[s] = 0;

    memset(c,0,sizeof(c));///c数组表示的是某一个节点的入队次数

    memset(vis,0,sizeof(vis));///一如既往的标记数组

    q.push(s);  vis[s] = 1; c[s] = 1;

    ///顶点入队vis要做标记，另外要统计顶点的入队次数

    int OK = 1;///OK用来表示是否有最短路径

    while(!q.empty())

    {

        int x;

        x = q.front(); q.pop();  vis[x]=0;

        ///队头元素出队，而且消除标记

        for(int k = next[x]; k != -1; k = edge[k].next) ///遍历顶点x的邻接表

        {                                 ///可是我个人认为这样的表示邻接表的方法不大好用

            int y = v[k];                   ///用vector<int> g[maxn]; 应该更好理解

            if(d[x] + w[k] < d[y])

            {

                d[y] = d[x] + w[k];  ///松弛

                if(!vis[y])          ///顶点y不在队内

                {

                    vis[y] = 1;      ///标记

                    c[y] ++;          ///统计次数

                    q.push(y);       ///入队

                    if(c[y]>NN)      ///超过入队次数上限，说明有负环

                        return OK=0;

                }

            }

        }

    }

    return OK;

}

这里须要注意的是 在读取边的过程中，对边的存储方式 这将关系到你在遍历与u相连的节点时 须要操作的内容

上面的存储方式并不好，有更好的存边方式。在这里就直接介绍SPFA的用法，不再赘述了

在这里给出一个链接 。里面有SPFA的更具体的介绍和证明。以及SPFA的dfs实现。有兴趣的同学能够进去看看~ ________SPFA链接biu~