bool SPFA(int s)
{
int cnt=0;
memset(dis,0x3f,sizeof(dis));
queue<int> q;
q.push(s);
vis[s]=1;dis[v]=0;
while(!q.empty())
{
int u=q.front();q.pop();
vis[u]=0;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i].v,w=g[u][i].w;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
cnt[v]=cnt[u]+1;
if(cnt[v]>=n) return true;//有负环
if(!vis[v])
{
q.push(v);
vis[v]=1;
}
}
}
}
return false;
}
void dijkstra(int s)
{
memset(dis,0x3f,sizeof(dis));
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
q.push({0,s});
dis[s]=0;
while(!q.empty())
{
int u=q.top().second;q.pop();
if(vis[u]) continue ;
vis[u]=1;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i].v,w=g[u][i].w;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
q.push({dis[v],v});
}
}
}
}
标签:cnt,int,dijkstra,vis,SPFA,&&,push,dis
From: https://www.cnblogs.com/After17/p/18378077