题解

SPFA算法
铃铛人加福特升级版

#include <cjdst.h>
struct node{
	int to, len;
};
vector <node> v[1005];//创建图
bool inqueue[1005];//记录是否在队列内
int dis[1005], vis[1005];//记录距离及被遍历多少次
int n, m, k, x, y, z;
bool spfa(){
	memset(dis, 63, sizeof(dis));
	queue <int> q;
	q.push(k), inqueue[k] = 1, dis[k] = 0;
	while(!q.empty()){
		int head = q.front();
		q.pop();
		inqueue[head] = 0, vis[head]++;//出队，并且遍历数加一
		if(vis[head] >= n) return 0;//如果大于等于n说明存在负环
		for(auto it:v[head]){
			if(dis[head] + it.len < dis[it.to]){
				dis[it.to] = dis[head] + it.len;//如果可以缩短距离
				if(!inqueue[it.to]){//并且不在队列
					q.push(it.to), inqueue[it.to] = 1;//直接入队
				}
			}
		}
	}
	return 1;
}
int main(){
	n = read(), m = read(), k = read();
	for(int i = 1; i <= m; i++){
		x = read(), y = read(), z = read();
		v[x].push_back({y, z});
	}
	if(!spfa()) cout << "no solution";
	else for(int i = 1; i <= n; i++) cout << (dis[i] == 0x3f3f3f3f ? -1 : dis[i]) << ' ';

	return 0;
}