把每个连通块做拓扑，在连通块内做djk

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int,int> pii;

const int N = 25010, M = 150010, INF = 0x3f3f3f3f;

int n,mr,mp,S;
int h[N],e[M],ne[M],idx,st[N],id[N],w[M];

vector <int> block[N];
//连通块数量
int bcnt;
int dist[N],din[N];

queue <int> q;

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

void dfs(int u,int bid)
{
    id[u]=bid;
    block[bid].push_back(u);

    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!id[j]) dfs(j,bid);
    }
}

void djk(int block_id)
{
    priority_queue<pii, vector<pii>, greater<pii>> heap;

    //取出该连通块所有的点, 入堆
    for(int u : block[block_id])
    {
        heap.push({dist[u], u});
    }

    while(heap.size())
    {
        pii t = heap.top();
        heap.pop();
        int u = t.second;

        if(st[u]) continue;
        st[u] = true;

        for(int i = h[u]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[u] + w[i])
            {
                dist[j] = dist[u] + w[i];
                if(id[j] == block_id) heap.push({dist[j], j});
            }

            if(id[j] != block_id && --din[id[j]] == 0) q.push(id[j]);
        }

    }
}


void top()
{
    memset(dist,0x3f,sizeof dist);
    dist[S]=0;
    for(int i=1;i<=bcnt;i++)
    {
        //如果一个点入度为0，将其加入队列
        if(!din[i])
            q.push(i);
    }
    while(q.size())
    {
        int t=q.front();
        q.pop();
        //cout<<1<<endl;
        djk(t);
    }

}


int main()
{
    scanf("%d%d%d%d",&n,&mr,&mp,&S);
    memset(h,-1,sizeof h);

    while(mr--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    for(int i=1;i<=n;i++)
    {
        if(!id[i])
            dfs(i,++bcnt);
    }

    while(mp--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        din[id[b]]++;
    }

    top();
    for(int i=1;i<=n;i++)
    {
        if(dist[i]>0x3f3f3f3f/2) cout<<"NO PATH"<<endl;
        else
        cout<<dist[i]<<endl;
    }
    return 0;
}

二刷，注意点已写在注释中,另外注意M别开小

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;
typedef pair<int,int> pii;

const int N = 25010, M = 150010;
int h[N],e[M],ne[M],w[M],idx;
int st[N],dist[N];
int n,r,p,s;
int id[N];
int id_cnt;
int din[N];

vector<int> block[N];
queue<int> q;


void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

void dfs(int u,int bid)
{
    id[u]=bid;
    block[bid].push_back(u);

    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!id[j]) dfs(j,bid);
    }
}

void djk(int bid)
{
    priority_queue<pii,vector<pii>,greater<pii>> heap;
    for(auto t:block[bid])
    {
        //注意此处push进去的是dist[u]，而不是0或其他的
        heap.push({dist[t],t});
    }

    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int ver=t.second;
        int dis=t.first;
        if(st[ver]) continue;
        st[ver]=1;

        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dis+w[i])
            {
                dist[j]=dis+w[i];
                if(id[j]==id[ver])
                {
                    heap.push({dist[j],j});
                }
            }
            if(id[j]!=id[ver])
            {
                din[id[j]]--;
                if(din[id[j]]==0) q.push(id[j]);
            }

        }
    }
}

void top()
{
    memset(dist,0x3f,sizeof dist);
    dist[s]=0;
    for(int i=1;i<=id_cnt;i++)
    {
        if(din[i]==0) q.push(i);
    }

    while(q.size())
    {
        int t=q.front();
        q.pop();
        //保证每个连通块只会入队一次
        djk(t);
    }
}


int main()
{
    cin>>n>>r>>p>>s;
    memset(h,-1,sizeof h);
    for(int i=1;i<=r;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }


    for(int i=1;i<=n;i++)
    {
        if(!id[i])
        {
            //这里必须是++id_cnt,不能是id_cnt++,因为不能让把一个点的连通块的编号赋值为0!!这样就和初始状态没区别！
            dfs(i,++id_cnt);
        }
    }

    for(int i=1;i<=p;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        din[id[b]]++;
    }

    top();

    for(int i=1;i<=n;i++)
    {
        if(dist[i]>0x3f3f3f3f/2)
        {
            cout<<"NO PATH"<<endl;
        }
        else
        cout<<dist[i]<<endl;

    }

    return 0;

}

三刷，debug了很久，终于过去了，算是自己写出来了

总结一下，思路清晰很重要：
对于这类有双向，有单向的题，要分成连通块，连通块内时双向边，块内djk，连通块外做top
具体步骤如下：
1. 分块，双向边连成的点为一个连通块
2. 大函数为top，先把入度为0的“块”加入队列
3. 对块内所有点做djk：依次将块内所有点放入堆中，由于小根堆的性质，优先算距离最近的点
4. 在更新距离时需要注意：如果两个点不在一个连通块内不能更新距离，不能入堆！
5. 若两个点不在一个连通块内，入点的连通块入度–，若之后入度为0，则入队，返回步骤3。若在一个连通块内，更新距离。

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 25010, M = 150010;
int h[N],e[M],ne[M],w[M],idx;
int st[N];
int din[N];
int dist[N];
int n,r,p,s;

typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii>> heap;
queue<int> q;
vector<int> block[N];
int bid[N];
int idcnt;


void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

void dfs(int u,int id)
{
    bid[u]=id;
    block[id].push_back(u);
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(bid[j]!=0) continue;
        dfs(j,id);
    }

}

void djk()
{

    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int u=t.second;
        int d=t.first;

        if(st[u]) continue;
        st[u]=1;

        for(int i=h[u];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[u]+w[i])
            {
                dist[j]=dist[u]+w[i];
                if(bid[j]==bid[u])
                    heap.push({dist[j],j});
            }
            if(bid[j]!=bid[u])
            {
                din[bid[j]]--;
                if(din[bid[j]]==0)
                {
                    q.push(bid[j]);
                }
            }

        }
    }
}

void top()
{
    memset(dist,0x3f,sizeof dist);
    dist[s]=0;

    for(int i=1;i<=idcnt;i++)
    {
        if(din[i]==0)
        {
            q.push(i);
        }
    }

    while(q.size())
    {
        int t=q.front();
        q.pop();

        for(int i=0;i<block[t].size();i++)
        {
            int ver=block[t][i];
            heap.push({dist[ver],ver});
        }
        djk();

    }
}


int main()
{
    cin>>n>>r>>p>>s;
    memset(h,-1,sizeof h);
    //道路连接成一个个连通块
    for(int i=1;i<=r;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    for(int i=1;i<=n;i++)
    {
        if(bid[i]==0)
        {
            idcnt++;
            dfs(i,idcnt);
        }
    }

    for(int i=1;i<=p;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        //b所在的连通块的入度++
        din[bid[b]]++;

    }
    for(int i=1;i<=idcnt;i++)
    {
        //cout<<din[i]<<endl;
    }

    //cout<<block[1].size();
    top();

    for(int i=1;i<=n;i++)
    {
        if(dist[i]>0x3f3f3f3f/2) cout<<"NO PATH"<<endl;
        else
        cout<<dist[i]<<endl;
    }

    return 0;
}

2023/12/21

复习了很久做出来了，总结一下思路：
双向道路内部做djk。
单向道路外部做拓扑。
1. 先用双向道路生成连通块
2. 单向道路计算每个连通块的入度
3. 把入度为0的连通块入队
4. 将连通块内的所有点，放入小根堆，做djk
5. 在djk过程中：当前点为v，v的邻点为j
如果dist[j]需要更新，且v和j在同一个连通块中，则将j加入堆中
注意：不论dist[j]是否需要更新，只要v和j不在一个连通块中，j所在的连通块的入度都要–；而不是只有dist[j]需要更新时，入度才–

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N=150100;
int e[N], ne[N], w[N], h[N], idx;
int st[N], dist[N];
int n, m, p, s;
int din[N];

// 连通块，每个连通块中有若干个点
vector<int> block[N];
// 每个点在哪个连通块中
int v2b[N];
// 拓扑队列
queue<int> q;
// djk小根堆
priority_queue<PII, vector<PII>, greater<PII>> heap;
// 初始化连通块序号
int bid = 1;

void add(int a,int b,int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}

void dfs(int u,int bid)
{
    v2b[u] = bid;
    block[bid].push_back(u);
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(v2b[j] == 0)
        {
            dfs(j, bid);
        }
    }
}


void djk()
{
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int d = t.first;
        int v = t.second;

        if(st[v]) continue;
        st[v] = 1;

        for(int i=h[v];i!=-1;i=ne[i])
        {
            int j = e[i];

            if(dist[j] > dist[v] + w[i])
            {
                dist[j] = dist[v] + w[i];
                // 如果v和j在一个连通块中，则之间入堆
                if(v2b[v] == v2b[j])
                {
                    heap.push({dist[j], j});
                }
            }
            // 否则, j所在的连通块的入度--, 如果入度为0, 则将j所在的连通块加入q
            // 注意，这里一定要放在上个if外面：
            // 不能仅在 dist[j] > dist[v] + w[i] 时，减入度，遍历到这个点就得减入度
            if(v2b[j]!=v2b[v])
            {
                din[v2b[j]]--;
                if(din[v2b[j]] == 0)
                {
                    q.push(v2b[j]);
                }
            }
        }

    }

}


void top()
{
    // 入度为0的连通块入队
    for(int i=1;i<=bid-1;i++)
    {
        if(din[i]==0)
        {
            q.push(i);
        }
    }

    dist[s] = 0;


    while(q.size())
    {
        int t = q.front();
        q.pop();

        // 把该连通块内的所有点加入小根堆
        for(int i=0;i<block[t].size();i++)
        {
            int var = block[t][i];
            heap.push({dist[var], var});
        }
        djk();
    }




}

// 连通块内djk， 连通块外拓扑
int main()
{
    memset(h, -1, sizeof(h));
    memset(dist, 0x3f, sizeof(dist));


    cin>>n>>m>>p>>s;

    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    // 初始化block的序号
    for(int i=1;i<=n;i++)
    {
        if(v2b[i] == 0)
        {
            dfs(i, bid);
            bid++;
        }
    }

    // for(int i=1;i<=n;i++)
    // {
    //     cout<<v2b[i]<<endl;
    // }

    // block的入度，在这初始化
    for(int i=1;i<=p;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        int bid = v2b[b];
        din[bid]++;
    }

    top();


    for(int i=1;i<=n;i++)
    {
        if(dist[i] > 0x3f3f3f3f/2)
        {
            cout<<"NO PATH"<<endl;
        }
        else cout<<dist[i]<<endl;
    }



    return 0;
}