题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

//spfa 会被卡，因此不能用spfa；

//拓扑排序 + dijkstra；
#include<iostream>
#include<cstring>
#include<queue>

#define x first;
#define y second;

using namespace std;

typedef pair<int, int> PII;

const int N = 25010, M = 150010, INF = 0x3f3f3f3f;
int dist[N];
bool st[N];
int h[N], e[M], ne[M], w[M], idx;
int id[N], idcnt;
int din[N];
vector<int> block[N];
queue<int> q;
int n, r, p, s;



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

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

void dijkstra(int bid)
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    for (auto item : block[bid]) heap.push({dist[item], item});

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

        int u = t.y;
        if (st[u]) continue;
        st[u] = true;

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

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

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

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        dijkstra(t);
    }

}

int main()
{
    cin >> n >> r >> p >> s;
    memset(h, -1, sizeof h);
    while(r --)
    {
        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])
            dfs(i, ++ idcnt);

    while(p --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        din[id[b]] ++;
    }

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

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla