SPFA+链式前向星

板子
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll inf=2<<30-1;

const ll maxn=599999;

ll head[maxn*2],cnt=1,n,m,s,dis[maxn];

struct edge{

	ll to,w,nxt;

}d[maxn];

queue<ll>q;

bool vis[maxn];

void add(int u,int v,int w){

	d[cnt].to=v,d[cnt].nxt=head[u];

	d[cnt].w=w;head[u]=cnt++;

}

void spfa(ll s)

{

	memset(vis,0,sizeof(vis));

	for(int i=0;i<=n;i++)	dis[i]=inf;

	dis[s]=0;q.push(s);vis[s]=1;

	while(!q.empty())

	{

		ll ans=q.front();q.pop();vis[ans]=0;

		for(int i=head[ans];i;i=d[i].nxt)

		{

			if(dis[d[i].to]>dis[ans]+d[i].w)

			{

				dis[d[i].to]=dis[ans]+d[i].w;

				if(!vis[d[i].to])//没在队列中

				{

					vis[d[i].to]=1;

					q.push(d[i].to);

				}

			}

		}

	}

}

int main()

{

	cin>>n>>m>>s;

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

	{

		int l,r,w;

		cin>>l>>r>>w;

		add(l,r,w);

	}

	spfa(s);

}
巴特西

SPFA+链式前向星

最新文章

热门文章
