H - Delivery Route ——dij + scc + topo

H - Delivery Route

题意

给你n个点的一张图，有x条无向边和y条有向边，每条边都有一个边权，但保证负边权不在环中，给你一个起始点，问你起始点每个点的最短路。
因为有负边，所以dij无法直接用，但是题目保证，负边不会出现在环中，所以我们可以强连通缩点，然后就变成了一个dag，对于这个dag，我们就直接topo计算每个强连通分量到s点的距离。
然后我们再在强连通分量中进行dij更新么个点的最短路即可。
对于每个强连通分量，我们不知道里面哪一个点是源点，所以对于每个与其他连通块联通的点都要作为源点计算一次dij
然后对于topo 因为我们已经用tarjan过了 强连通的编号就是逆topo序。

#include<bits/stdc++.h>
#include<array>
#define ll long long
#define all(a) a.begin(),a.end()
using namespace std;

const int N = 2e5 + 505;
const int M = 1e6 + 1;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;

int x, y, s, n;
int dfn[N], low[N], sc, c[N], tot, dis[N];
int vis[N], in[N];
map<pair<int, int>, int>mp;
vector<pair<int, int>>g[N], g2[N];
vector<int>root[N], scc[N];
stack<int>st;

void tarjan(int x) {
    dfn[x] = low[x] = ++tot;
    st.push(x);
    in[x] = 1;
    for (auto [to, w] : g[x]) {
        if (!dfn[to]) {
            tarjan(to);
            low[x] = min(low[x], low[to]);
        }
        else if (in[to]) {
            low[x] = min(low[x], dfn[to]);
        }
    }

    if (low[x] == dfn[x]) {
        sc++;
        while (1) {
            int now = st.top();
            st.pop();
            in[now] = 0;
            c[now] = sc;
            scc[sc].push_back(now);
            if (now == x) break;
        }
    }
}

void dij(int s) {
    for (int i = 1; i <= n; i++) vis[i] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
    q.push({ dis[s], s });
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (auto [to, w] : g[x]) {
            if (c[to] != c[x]) continue;
            if (dis[to] > dis[x] + w) {
                dis[to] = dis[x] + w;
                q.push({ dis[to], to });
            }
        }
    }
}

void solve() {
    cin >> n >> x >> y >> s;
    int u, v;
    ll w;

    for (int i = 1; i <= x; i++) {
        cin >> u >> v >> w;

        g[u].push_back({ v, w });
        g[v].push_back({ u, w });
    }

    for (int i = 1; i <= y; i++) {
        cin >> u >> v >> w;
        g[u].push_back({ v, w });
    }

    tarjan(s);

    //记录每个强连通分量需要作为源点的点
    for (int i = 1; i <= n; i++) {
        for (auto [to, w] : g[i]) {
            if (c[to] != c[i]) {
                if (!mp[{i, to}]) {
                    // g2[c[i]].push_back({ c[to], w });
                    root[c[to]].push_back(to);
                    mp[{i, to}] = 1;
                }
            }
        }
    }
    root[c[s]].push_back(s);

    for (int i = 1; i <= n; i++) dis[i] = inf;
    dis[s] = 0;
    //topo
    for (int i = sc; i >= 1; i--) {
        for (auto it : root[i]) dij(it);
        for (auto x : scc[i])
            for (auto [to, w] : g[x])
                dis[to] = min(dis[to], dis[x] + w);
    }

    for (int i = 1; i <= n; i++) {
        if (dis[i] >= inf) cout << "NO PATH\n";
        else cout << dis[i] << '\n';
    }

}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int _t = 1;
    //cin >> _t;
    while (_t--) {
        solve();
    }

    return 0;
}