spfa普通版就不写了,优化还是要的昂,spfa是可以判负环,接受负权边和重边的,判断负环只需要另开一个数组记录每个结点的入队次数,当有任意一个结点入队大于点数就表明有负环存在
#include<stdio.h> //spfa基本上要这些头文件
#include<string.h>
#include<queue>
using namespace std; const int maxn=1e5+;
const int maxm=1e5+;
const int INF=0x3f3f3f3f; int head[maxn],point[maxm<<],nxt[maxm<<],val[maxm<<],size;
int dis[maxn],vis[maxn]; void init(){
memset(head,-,sizeof(head));
size=;
} void add(int a,int b,int v){ //有向图只需要前一半
point[size]=b;
val[size]=v;
nxt[size]=head[a];
head[a]=size++; point[size]=a;
val[size]=v;
nxt[size]=head[b];
head[b]=size++;
} void spfa(int s,int t){
memset(vis,,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
queue<int>q;
vis[s]=;
dis[s]=;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=;
for(int i=head[t];~i;i=nxt[i]){
int j=point[i];
if(dis[j]>dis[u]+val[i]){
dis[j]=dis[u]+val[i];
if(!vis[j]){
q.push(j);
vis[j]=;
}
}
}
}
printf("%d\n",dis[t]);
}