求关注~

每日一篇题解，身体很健康~

SPFA经典模板题
代码如下

#include <bits/stdc++.h>
using namespace std;

int n, m, s;
struct node{
	int v, w;
};

vector<node> h[100001];
int x, y;
int d[100001];
int cnt[100001];

int main(){
	cin >> n >> m >> s;
	while (m--){
		int u, v, w;
		cin >> u >> v >> w;
		h[u].push_back({v, w});
	}
	
	memset(d, 0x3f, sizeof d); 
	queue<int> q;
	q.push(s);
	d[s] = 0;
	while (q.size()){
		int u = q.front();
		q.pop();
		cnt[u]++;
		if (cnt[u] >= n){
			cout << "no solution";
			return 0;
		}
		for (node t: h[u]){
			int v = t.v, w = t.w;
			if (d[v] <= d[u] + w) continue;
			d[v] = d[u] + w;
			q.push(v);
		}
	}
	
	for (int i = 1; i <= n; i++){
		if (d[i] == 0x3f3f3f3f) cout << -1 << " ";
		else cout << d[i] << " ";
	}
	
	return 0;
}

随时可以问我问题，前提是关注！