其他链接
来自以上题解的图片来自常暗踏阴
使用前向星链表存图
直接用队列优化spfa
struct cmp
{
bool operator()(int a,int b)
{
return dist[a]>dist[b];
}
}; priority_queue<int,vector<int>,cmp> q;void dijspfa()
{
q.push(s);
memset(inq,,sizeof(inq));
memset(dist,0x7f,sizeof(dist));
dist[s]=;
while(!q.empty())
{
int u=q.top();
q.pop();inq[u]=;
for(int j=first[u];j>;j=e[j].nxt)
{
if(e[j].len+dist[u]<dist[e[j].to])
{
dist[e[j].to]=dist[u]+e[j].len;
if(inq[e[j].to]==)
{
q.push(e[j].to);inq[e[j].to]=;
}
}
}
}
}
dijspfa特性
1.判负环
spfa判负环主要用dfs，因为dfs判负环可以及时退出防止超时，
数据强化可以用bfs看下面
dijspfa判负环继承spfa的功能
但是可能过不了233
SPjkstra算法--就是本文的dijspfa
2.与dij，spfa比较
dij的思想是堆优化后从小到大松弛，每个点只入队一次
spfa的思想是不断修改子节点，使每个点重复入队更新，因此可以判负环
时间差异就在重复入队上
完整代码
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#define Mx 200001
#define Nx 100001
using namespace std;
struct edge
{
int to,nxt,len;
}e[Mx];
int first[Nx]; int n,m,s;
void addstar(int i,int u,int v,int w)
{
e[i].len=w;
e[i].nxt=first[u];
e[i].to=v;
first[u]=i;
}
int inq[Nx];
int dist[Nx]; struct cmp
{
bool operator()(int a,int b)
{
return dist[a]>dist[b];
}
}; priority_queue<int,vector<int>,cmp> q;
void dijspfa()
{
q.push(s);
memset(inq,,sizeof(inq));
memset(dist,0x7f,sizeof(dist));
dist[s]=;
while(!q.empty())
{
int u=q.top();
q.pop();inq[u]=;
for(int j=first[u];j>;j=e[j].nxt)
{
if(e[j].len+dist[u]<dist[e[j].to])
{
dist[e[j].to]=dist[u]+e[j].len;
if(inq[e[j].to]==)
{
q.push(e[j].to);inq[e[j].to]=;
}
}
}
}
}
int main()
{
memset(first,,sizeof(first));
cin>>n>>m>>s;
for(int i=;i<=m;++i)
{
int a,b,c;
cin>>a>>b>>c;
addstar(i,a,b,c);
}
dijspfa();
for(int i=;i<=n;++i)
{
cout<<dist[i]<<" ";
}
return ;
}