void spfa()
{
int index,i;
while(!Q.empty())
{
index=Q.front();
Q.pop();
for(i=0;i<edge[index].size();i++)
{
if(dist[edge[index][i].id]<dist[index]+edge[index][i].fa)
{ dist[edge[index][i].id]=dist[index]+edge[index][i].fa;
//if(index!=mm)
//mark[index]=0;
flag[edge[index][i].id]++;
if(flag[edge[index][i].id]>vv)
return ;
if(!mark[edge[index][i].id])
{
Q.push(edge[index][i].id);
mark[edge[index][i].id]=true;
}
}
}
mark[index]=0;
}
return ;
}

mark标记节点是否在队列里。

edge[i][j]以i节点为起点的第j条边

dist[i]从源点到第i个节点的路径长

flag[i]第i个节点进行了多少次松弛操作。

vv路径最大值