思路

非负道路形成连通块，航线保证块间有向无环；按拓扑序在每块用多源Dijkstra再松弛负权航线，不能直接对含负权全图用Dijkstra；不可达块也要消去出边入度，严格输出NO PATH。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,R,P,S;cin>>n>>R>>P>>S;--S;vector<vector<pair<int,int>>>road(n),flight(n);vector<int>parent(n),size(n,1);iota(parent.begin(),parent.end(),0);function<int(int)>find=[&](int x){return parent[x]==x?x:parent[x]=find(parent[x]);};for(int i=0;i<R;i++){int u,v,w;cin>>u>>v>>w;--u;--v;road[u].push_back({v,w});road[v].push_back({u,w});int a=find(u),b=find(v);if(a!=b){if(size[a]<size[b])swap(a,b);parent[b]=a;size[a]+=size[b];}}vector<int>comp(n),index(n,-1);int total=0;for(int v=0;v<n;v++){int root=find(v);if(index[root]<0)index[root]=total++;comp[v]=index[root];}vector<vector<int>>vertices(total);for(int v=0;v<n;v++)vertices[comp[v]].push_back(v);vector<int>indegree(total);for(int i=0;i<P;i++){int u,v,w;cin>>u>>v>>w;--u;--v;flight[u].push_back({v,w});indegree[comp[v]]++;}queue<int>q;for(int c=0;c<total;c++)if(!indegree[c])q.push(c);const long long INF=(1LL<<60);vector<long long>d(n,INF);d[S]=0;while(!q.empty()){int c=q.front();q.pop();priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>heap;for(int v:vertices[c])if(d[v]!=INF)heap.push({d[v],v});while(!heap.empty()){auto p=heap.top();heap.pop();int v=p.second;if(p.first!=d[v])continue;for(auto e:road[v])if(d[e.first]>d[v]+e.second){d[e.first]=d[v]+e.second;heap.push({d[e.first],e.first});}}for(int v:vertices[c])for(auto e:flight[v]){if(d[v]!=INF)d[e.first]=min(d[e.first],d[v]+e.second);if(--indegree[comp[e.first]]==0)q.push(comp[e.first]);}}for(long long value:d){if(value==INF)cout<<"NO PATH\n";else cout<<value<<'\n';}}