【最短路】洛谷 P3371 【模板】单源最短路径（弱化版）

题链

#include <bits/stdc++.h>
using namespace std;
#define MS 10009
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define MAXN 2147483647

int n,m;
int st;
struct node{
	int to,val;
};
vector<node > vc[MS];
int dis[MS];
bool v[MS];

void dijkstra(){
	// 除了源点，其余初值为 MAXN 
	for(int i=1;i<=n;i++){
		v[i] = 0;
		dis[i] = MAXN;
	} 
	dis[st] = 0;
	
	while(!v[st]){
		int minn = MAXN;
		v[st] = 1;
		for(auto &i:vc[st]){ // 松弛 
			if(!v[i.to] && dis[st]+i.val < dis[i.to]){
				dis[i.to] = dis[st] + i.val;
			}
		}
		for(int i=1;i<=n;i++){ // 取未被访问的最近的点 
			if(!v[i] && dis[i] < minn){
				minn = dis[i];
				st = i;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> st;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		vc[u].push_back({v,w});
	}
	
	dijkstra();
	
	for(int i=1;i<=n;i++){
		cout << dis[i] << " ";
	}
	cout << "\n";
	
	
	return 0;
}