• 优先队列:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,s;
vector<pair<int,int>> g[N];//f w,s u
int d[N];
bool f[N];
void dijkstra(){
	priority_queue<pair<int,int>> q;//f w,s u
	memset(d,0x3f,sizeof(d));
	d[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(f[u])continue;
		f[u]=true;
		for(auto &i:g[u]){
			int v=i.second,w=i.first;
			if(d[u]+w<d[v]){
				d[v]=d[u]+w;
				q.push(make_pair(-d[v],v));
			}
		}
	}
 return;
}
int main(){
	
	cin>>n>>m>>s;
	for(int i=1;i<=m;++i){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back(make_pair(w,v));//{w,v}
	}
	dijkstra();
	for(int i=1;i<=n;++i)
		cout<<d[i]<<' ';
	
 return 0;
} 

• O(n^2)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,s;
vector<pair<int,int>> g[N];//f u,s w
int d[N];
bool f[N];
void dijkstra(){
	memset(d,0x3f,sizeof(d));
	d[s]=0;
	for(int i=1;i<=n;++i){
		int mi=d[0],u=0;
		for(int j=1;j<=n;++j)
			if(!f[j]&&d[j]<mi)
				mi=d[j],u=j;
		f[u]=true;	
		for(auto &k:g[u]){
			int v=k.first,w=k.second;
			if(d[u]+w<d[v]){
				d[v]=d[u]+w;
			}
		}
		
	}
 return;
}
int main(){
	
	cin>>n>>m>>s;
	for(int i=1;i<=m;++i){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back(make_pair(v,w));
	}
	dijkstra();
	for(int i=1;i<=n;++i)
		cout<<d[i]<<' ';
	
 return 0;
}