最短路

需要注意树上做最短路是$O(n)$,因为只需要一次dfs

SPFA

#include<bits/stdc++.h>
using namespace std;
int n,m,ss; 
bool vis[500010];
int q[1000010],dis[500010];
vector<int>head,to,nxt,val;
void add(int u,int v,int w)
{
	nxt.push_back(head[u]);
	head[u]=to.size();
	to.push_back(v);
	val.push_back(w);
}
void SPFA(int s)
{
	int l=0,r=0;
	for(int i=1;i<=n;++i)
	{
		dis[i]=0x3f3f3f3f;
	}
	dis[s]=0;
	q[r]=s;
	vis[s]=1;
	while(l<=r)
	{
		int x=q[l];
		for(int i=head[x];i!=-1;i=nxt[i])
		{
			if(dis[to[i]]>dis[x]+val[i])
			{
				dis[to[i]]=dis[x]+val[i];
				if(!vis[to[i]])
				{
					q[++r]=to[i];
					vis[to[i]]=1;
				}
			}
		}
		vis[x]=0;
		++l;
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&ss);
	head.resize(n+1,-1);
	for(int i=1;i<=m;++i)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	SPFA(ss);
	for(int i=1;i<=n;++i)
	{
		printf("%d ",dis[i]!=0x3f3f3f3f?dis[i]:2147483647);
	}
    return 0;
}

dijkstra

#include<bits/stdc++.h>
using namespace std;
int n,m,ss; 
bool vis[100010];
int dis[100010];
vector<int>head,to,nxt,val;
struct node
{
	int d,x;
};
struct cmp
{
	bool operator()(node x,node y)
	{
		return x.d>y.d;
	}
};
void add(int u,int v,int w)
{
	nxt.push_back(head[u]);
	head[u]=to.size();
	to.push_back(v);
	val.push_back(w);
}
priority_queue<node,vector<node>,cmp>q;
void dijkstra(int s)
{
	for(int i=1;i<=n;++i)
	{
		dis[i]=1e9;
	}
	dis[s]=0;vis[s]=1;
	node tmp;
	tmp.x=s;tmp.d=0;
	q.push(tmp);
	while(!q.empty())
	{
		int x=q.top().x;
		vis[x]=0;
		q.pop();
		for(int i=head[x];i!=-1;i=nxt[i])
		{
			if(dis[to[i]]>dis[x]+val[i])
			{
				dis[to[i]]=dis[x]+val[i];
				if(!vis[to[i]])
				{
					tmp.x=to[i];tmp.d=dis[to[i]];
					q.push(tmp);
					vis[to[i]]=1;
				}
			}
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&ss);
	head.resize(n+1,-1);
	for(int i=1;i<=m;++i)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	dijkstra(ss);
	for(int i=1;i<=n;++i)
	{
		printf("%d ",dis[i]);
	}
    return 0;
}