关于spfa
  • 板块灌水区
  • 楼主Watanabe
  • 当前回复21
  • 已保存回复21
  • 发布时间2022/11/7 13:22
  • 上次更新2023/10/27 03:57:06
查看原帖
关于spfa
631787
Watanabe楼主2022/11/7 13:22

rt,求问这个算不算spfa

#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1000010;
long long n,m;
long long h[N],net[N],e[N],neg[N],idx;
priority_queue < pair < int , int > > d;
//queue <int > d;
void jb(int x,int y,int qz)
{
	e[++idx]=y,neg[idx]=qz,net[idx]=h[x],h[x]=idx;
}
long long dist[N],q;
bool v[N];
void spfa()
{
     for(int i=1;i<=n;++i)
     {
     	dist[i]=2147483647,v[i]=0;
     }
     dist[q]=0;
     //d.push(q);
     d.push(make_pair(0,q));
     while(d.size())
     {
     	//int x=d.front();
     	int x=d.top().second;
     	d.pop();
     	v[x]=0;
     	for(int i=h[x];i;i=net[i])
     	{
     		int j=e[i];
     		if(dist[j]>dist[x]+neg[i])
     		{
     			dist[j]=dist[x]+neg[i];
				 if(!v[j])
     			{
     				v[j]=1;
     				//d.push(j);
     				d.push(make_pair(-dist[j],j));
     			}
     		}
			    
     	}
     }
     return ;
}
int main()
{
	scanf("%d %d %d",&n,&m,&q);
	for(int i=1;i<=m;++i)
	{
		int x,y,qz;
		scanf("%d%d%d",&x,&y,&qz);
		jb(x,y,qz);
	}
	spfa();
	for(int i=1;i<=n;++i)
	{
		printf("%d ",dist[i]);
	}
	return 0;
}
2022/11/7 13:22
加载中...