分析

本题给出的道路和航线其实就是单向道路和双向道路
所以我们直接正常建边就可了
由于题目保证了不存在环，那么就绝对没有负环情况
但因为有负边，所以我们需要用SPFA
所以我们直接套板子即可
当然，这里我们使用SPFA的优化（slf优化 或者 lll优化）
（机房大佬说想要不一样就要Tarjan缩点+Dijkstra）

代码

//LOJ 10081
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
#include <cmath>
#include <cstring>

#define LL long long
#define Lowbit(X) (X&(-X))
#define Lson (X<<1)
#define Rson (X<<1|1)
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(int i=A;i<=B;i++)
#define BOR(i,A,B) for(int i=A;i>=B;i--)
#define FOR_SIDE(i,A) for(int i=Head[A];i;i=Next[i])
#define INF 0x3f3f3f3f
using namespace std;
const int MaxN=1e5+10;

int Sta,Total,Side,R,P;
int u,v,w,Opt,Dist[MaxN];
bool Vis[MaxN];
int Next[MaxN<<1],End[MaxN<<1],Cur,Head[MaxN],Val[MaxN<<1];
deque<int>Temp;

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline void Add_Edge(int From,int To,int Temp) {
    Next[++Cur]=Head[From];
    Head[From]=Cur;
    End[Cur]=To;
    Val[Cur]=Temp;
}

inline void SPFA() {
    Cl(Dist,0x3f);
    Dist[Sta]=0;
    Vis[Sta]=true;
    Temp.push_front(Sta);
    while(!Temp.empty()) {
        int New=Temp.front();
        Temp.pop_front();
        Vis[New]=false;
        FOR_SIDE(i,New) {
            if(Dist[End[i]]>Dist[New]+Val[i]) {
                Dist[End[i]]=Dist[New]+Val[i];
                if(!Vis[End[i]]) {
                    if(Temp.empty() || Dist[End[i]]<Dist[Temp.front()]) Temp.push_front(End[i]);
                    else Temp.push_back(End[i]);
                    Vis[End[i]]=true;
                }
            }
        }
    }
}

int main() {
    //File();
    scanf("%d %d %d %d",&Total,&R,&P,&Sta);
    Side=R+P;
    FOR(i,1,R) { scanf("%d %d %d",&u,&v,&w); Add_Edge(u,v,w); Add_Edge(v,u,w); }
    FOR(i,1,P) { scanf("%d %d %d",&u,&v,&w); Add_Edge(u,v,w); }
    SPFA();
    FOR(i,1,Total) {
        if(Dist[i]==INF) { printf("NO PATH\n"); }
        else { printf("%d\n",Dist[i]); }
    }
    //fclose(stdin); fclose(stdout);
    system("pause");
    return 0;
}