spfa 怎么解决 最长路的问题 （为无向图且保证出现正环）

SPFA可以处理负环，记录一个点出现的次数，只要这个点出现次数超过n次（n为总点数），就证明有负环

事实上，把正边权改为负边权是可以的，也很方便；但是有时SPFA可以直接修改算法中的大于号或小于号，这不适用于Dijkstra

边权取负是最常用的，题目一般会保证没有负环，如果有的话一般会让输出impossible这样的字串

下面是我SPFA的一个板子

#include<bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

struct Edge

{

int to,next,len;

}edge[(int)1e5+5];

struct Node

{

int head,dis;

bool vis;

}node[(int)1e5+5];

int cnt;

int addEdge(int u,int v,int w)

{

edge[++cnt].len=w;

edge[cnt].to=v;

edge[cnt].next=node[u].head;

node[u].head=cnt;

}

int u,v,w;

int n,m;

int SPFA()

{

queue<int>q;

for(int i=1;i<=n;i++)

{

node[i].dis=INF;

node[i].vis=false;

}

node[1].dis=0;

node[1].vis=true;

q.push(1);

while(not q.empty())

{

int u=q.front();

q.pop();

node[u].vis=false;

for(int e=node[u].head;e;e=edge[e].next)

{

int v;

if(node[v=edge[e].to].dis<=node[u].dis+edge[e].len)continue;

node[v].dis=node[u].dis+edge[e].len;

/*只要在这里加一个判断，

c[v]++;//更新出现次数

if(c[v]>n) return 0;*/

if(!node[v].vis)

{

q.push(v);

node[v].vis=true;

}

}

}

if(node[n].dis==INF)

{

puts("impossible");

exit(0);

}

return node[n].dis;

}

int main()

{

cin>>n>>m;

for(int i=1;i<=m;i++)

{

cin>>u>>v>>w;

addEdge(u,v,w);//根据题目要求是否取相反数

}

cout<<SPFA()<<endl;

return 0;

}

纯手打，很累，不理解继续问，求采纳