本文共 765 字，大约阅读时间需要 2 分钟。

板子

#include 
   
    using namespace std;typedef long long ll;const int inf=2<<30-1;const int maxn=599999;int head[maxn*2],cnt=1,n,m,s,dis[maxn];struct edge{	int to,w,nxt;}d[maxn];queue
    
     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(int 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())	{		int 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);}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/104373699 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！