BZOJ2200 拓扑排序+最短路

发表于 | 阅读数

给定一张图,有$R$条正权的双向边，$P$条正负权的有向边，求最短路$(n\leq10^5)$ 待理解了$dijkstra$

首先要知道$dijkstra$不能处理负权边的原因

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
using namespace std;

typedef long long ll;
#define inf 0x3f3f3f3f
const int N = 3e5 + 10;
const int mod = 1e9 + 7;
struct edge
{
    int to, w;
} e;
vector<edge> g[N];
void addedge(int u, int v, int w)
{
    e.to = v;
    e.w = w;
    g[u].push_back(e);
}
int n, r, p, s, f[N], vis[N], cnt, dis[N], dig[N];
queue<int> tuo;
priority_queue<pair<int, int>> q;
void dfs(int x)
{
    f[x] = cnt;
    vis[x] = 1;
    for (int i = 0; i < g[x].size(); i++)
        if (!vis[g[x][i].to])
            dfs(g[x][i].to);
}

int main()
{
    scanf("%d%d%d%d", &n, &r, &p, &s);
    for (int i = 1; i <= r; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w);
        addedge(v, u, w);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            ++cnt, dfs(i);
    //cout<<1<<endl;
    for (int i = 1; i <= p; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w);
        dig[f[v]]++;
    }
    //cout<<1<<endl;
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x7f, sizeof(dis));
    tuo.push(f[s]);
    for (int i = 1; i <= cnt; i++)
        if (!dig[i])
            tuo.push(i);
    dis[s] = 0;
    while (!tuo.empty())
    {
        int u = tuo.front();
        //cout<<u<<endl;
        tuo.pop();
        for (int i = 1; i <= n; i++)
            if (f[i] == u)
                q.push(make_pair(-dis[i], i));
        while (!q.empty())
        {
            int x = q.top().second;
            q.pop();
            if (vis[x])
                continue;
            vis[x] = 1;
            for (int i = 0; i < g[x].size(); i++)
            {

                int v = g[x][i].to;
                // cout<<v<<endl;
                // cout<<"----"<<endl;
                int w = g[x][i].w;
                if (dis[v] > w + dis[x])
                {
                    dis[v] = w + dis[x];
                    if (f[v] == f[x])
                        q.push(make_pair(-dis[v], v));
                }
                if (f[v] != f[x])
                {
                    dig[f[v]]--;
                    if (dig[f[v]] == 0)
                        tuo.push(f[v]);
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
        if (dis[i] >= inf)
            printf("NO PATH\n");
        else
            printf("%d\n", dis[i]);
}