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~