做法：SPFA+SLF

思路：

出现了负权边,那么我们可以使用SPFA做法
然后套用SPFA的板子，结果就t了最后2个点www
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44977509&returnHomeType=1&uid=427618442
然后使用SLF优化（它是一种利用双端队列算法处理的问题。将队列建成双端队列，在遇到要插入的点的最短路比当前的队头的最短路短就插入队首，否则插入队尾。）
成功水过

代码：

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=25010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int t,r,p,s;
int a,b,c;

struct node{
    int next,cost;
};

vector<node> g[N];
deque<int> q;
bool st[N];
int dis[N];

void spfa(int s){
    mst(dis,INF);dis[s]=0;
    q.pb(s);
    st[s]=1;
    while(!q.empty()){
        int t=q.front();
        q.pop_front();
        st[t]=0;
        for(auto v:g[t]){
            int j=v.next;
            if(dis[j]>dis[t]+v.cost){
                dis[j]=dis[t]+v.cost;
                if(!st[j]){
                    st[j]=1;
                    if(!q.empty()&&dis[j]<dis[q.front()]) q.push_front(j);
                    else q.pb(j);
                }
            }
        }
    }
}

void solve(){
    cin>>t>>r>>p>>s;
    _for(i,r){
        cin>>a>>b>>c;
        g[a].pb({b,c});
        g[b].pb({a,c});
    }
    _for(i,p){
        cin>>a>>b>>c;
        g[a].pb({b,c});
    }
    spfa(s);
    for(int i=1;i<=t;i++){
        if(dis[i]==INF) cout<<"NO PATH\n";
        else cout<<dis[i]<<"\n";
    }
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef DEBUG
    freopen("F:/laji/1.in", "r", stdin);
//    freopen("F:/laji/2.out", "w", stdout);
#endif
//     int t;cin>>t;while(t--)
    solve();
    return 0;
}

ps:

正解应该是DAG+toposort,因为太复杂所以就不想写了（主要是不会zz) (逃
下面贴一个细节回答拉满的链接 https://www.acwing.com/solution/content/3950/