题解（求赞）

再说代码之前，我先给大家讲个乐子：我那个班刚学SPFA算法，然后在上DJ的时候就有个天才用BFS写出来了（其实就是SPFA，只是没判负环而已），乐了一节课。

接下来进入正题
——————————————不怎么华丽的分界线——————————————
先介绍一下SPFA算法吧（都忘得差不多了，就讲个大概吧）

其主要流程其实和BFS差不多

0.5.出生
1.写基础框架
1.先搞一个队列q，然后就是BFS的while循环，里面还是判断q是否为空（懒人可用size代替）
2.在邻接表里找它能到的地方，给他松弛(不许玩梗)一下，顺便搞一个mp字典，看它是否被塞进去过，没塞进去过的话就把它塞进去，并标记。
2.5.在删除队头的时候记得把标记去掉！
3.搞一个vis数组，用于标记每一个点被塞进去的次数。
4.判断vis数组内的次数是否大于等于n，因为当其大于等于n时，那必定是出现了负环，直接输出+return 1，这里把BFS函数改成bool函数是判断是否出现负环。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m,s,run=0;
map<int,set<pair<int,int>>> maze;
map<int,bool> mp;
vector<int> ans(1005,100000000);
vector<int> vis(1005,0);
bool BFS(){
    queue<int> q;
    q.push(s);
    mp[s]=1;
    ans[s]=0;
    while(q.size()){
        int f=q.front();q.pop();
        mp[f]=0;
        vis[f]++;
        if(vis[f]>=n){
            cout<<"no solution";
            return 1;
        } 
        for(auto [i,j]:maze[f]){
            if(ans[i]>ans[f]+j){
                ans[i]=ans[f]+j;
                if(mp[i]==0){
                    q.push(i);
                    mp[i]=1;
                }
            }
        }
    }
    return 0;
}
int main(){
    cin>>n>>m>>s;
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        maze[x].insert({y,z});
    }
    int ok=BFS();
    if(ok) return 0;
    for(int i=1;i<=n;i++) cout<<((ans[i]==100000000)?-1:ans[i])<<' ';
	return 0;
}