Delivery Route(2019银川H题)

链接:https://nanti.jisuanke.com/t/42388
题意:n个点,x条无向边,y条有向边(存在负边权),一个起点s,然后求s到剩余点的最短路
题解:这题卡spfa......
然后看题解,写的用连通块加上Dijkstra,Dijkstra还能写负边权(???)
相同的连通块之内用Dijkstra,不同的Dijkstra用遍历........

#include <bits/stdc++.h>
using namespace std;
int n, x, y, s;
const int MAXN = 2e5 + 50;
typedef pair<int, int> pii;
#define mp make_pair

int head[MAXN], tot;
struct Edge
{
    int nex, to, dis;
}eg[MAXN];
void addedge(int a, int b, int c)
{
    eg[++tot] = {head[a], b, c};
    head[a] = tot;
}
void add(int a, int b, int c)
{
    addedge(a, b, c);
    addedge(b, a, c);
}

vector<int> bel[MAXN];
int co[MAXN], cnt;//联通块的颜色、联通块的数量
void dfs(int v, int col)//dfs给联通块染色
{
    co[v] = col;
    bel[col].push_back(v);
    for(int i = head[v]; i; i = eg[i].nex)
    {
        int to = eg[i].to;
        if(!co[to]) dfs(to, col);
    }
}

int deg[MAXN], dis[MAXN];//每个联通块的入度、单源最短路径
int vis[MAXN];
queue<int> que;//拓扑排序：入度为0的联通块入队
priority_queue<pii, vector<pii>, greater<pii> > pq;
void Dijkstra()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    for(int i = 1; i <= cnt; i++) if(!deg[i]) que.push(i);
    while(!que.empty())//topological-sort
    {
        int u = que.front(); que.pop();
        int sz = bel[u].size();
        for(int i = 0; i < sz; i++) pq.push(mp(dis[bel[u][i]], bel[u][i]));
        while(!pq.empty())//Dijkstra
        {
            int x = pq.top().second; pq.pop();
            if(vis[x]) continue;
            vis[x] = 1;
            for(int i = head[x]; i; i = eg[i].nex)
            {
                int to = eg[i].to;
                if(co[x] == co[to] && dis[to] > dis[x] + eg[i].dis)
                {
                    dis[to] = dis[x] + eg[i].dis;
                    pq.push(mp(dis[to], to));
                }
                if(co[x] != co[to])
                {
                    dis[to] = min(dis[to], dis[x] + eg[i].dis);
                    deg[co[to]]--;
                    if(!deg[co[to]]) que.push(co[to]);
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d%d%d", &n, &x, &y, &s);
    for(int i = 1, a, b, c; i <= x; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    for(int i = 1; i <= n; i++) if(!co[i]) dfs(i, ++cnt);
    for(int i = 1, a, b, c; i <= y; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        addedge(a, b, c);
        deg[co[b]]++;
    }
    Dijkstra();
    for(int i = 1; i <=n; i++)
    {
        if(dis[i] > 1e9) puts("NO PATH");
        else printf("%d\n", dis[i]);
    }
    return 0;
}