分析

读完题，我们发现这道题就是让你求出在一张混合图中的单源最短路。因为有负环，直接考虑 算法。因为题面上已经保证是没有负环的，所以一定有解。考虑到朴素的 算法容易被卡，这里使用 。将原队列改成双端队列，对要加入队列的点 ，如果 小于队头元素 的 ，将其插入到队头，否则插入到队尾。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 8e4 + 100,inf = 0x3f3f3f3f;
int n,P,R,S,dis[N],vis[N];
deque<int> Q;
vector<int> G[N],W[N];
void spfa(int s) {
    memset(dis,inf,sizeof(dis));dis[s] = 0;Q.push_back(s);vis[s] = 1;
    while(Q.size()) {
        int x = Q.front();Q.pop_front();vis[x] = 0;
        for(int i = 0;i < G[x].size();i++) {
            int y = G[x][i],d = W[x][i];
            if(dis[y] > dis[x] + d) {
                dis[y] = dis[x] + d;
                if(vis[y]) continue;
                vis[y] = 1;
                if(Q.empty()) Q.push_back(y);
                else {
                    if(dis[y] < dis[Q.front()]) Q.push_front(y);
                    else Q.push_back(y);
                }
            }
        }
    }
} 
int main()
{
    cin >> n >> R >> P >> S;
    for(int i = 1,a,b,c;i <= R;i++) {
        cin >> a >> b >> c;
        G[a].push_back(b);G[b].push_back(a);
        W[a].push_back(c);W[b].push_back(c);
    }
    for(int i = 1,a,b,c;i <= P;i++) {
        cin >> a >> b >> c;
        G[a].push_back(b);W[a].push_back(c);
    }
    spfa(S);
    for(int i = 1;i <= n;i++)
    dis[i] == inf ? puts("NO PATH"):printf("%d\n",dis[i]);
    return 0;
}