普通快乐

Posted on Edited on In

题目大意：这是一张 n 个点 m 条边的连通图。这张图上面有 k 个奇葩点。保证没有重边和自环。 现在要求你从其中任意一个奇葩点开始走，走到除了这个奇葩点以外的最近奇葩点。 问选择哪一个奇葩点开始走，路程最小。

暴力做法，对每一个奇葩点都跑一边dij或者spfa

考虑优化：（来自Aswert大佬做法)

你考虑对每一个点dij的时候，如果发现我们遇到的这个点就是奇葩点，就停止

因为我们第一次搜到他，无论是哪个点，距离一定是最小的

再加上快读优化，就过了，暴力碾标算

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
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pr;

const int N = 1e5 + 666, inf = 214748364;

priority_queue<pr, vector<pr>, greater<pr> >q;
int n, m, k, yhm(inf);
int c[N], dis[N], vis[N], tag[N];

inline void dij(int now)
{
    int i, x, y, fuck;
    for (i = 1; i <= n; ++ i) dis[i] = inf, vis[i] = 0;
    dis[now] = 0, vis[now] = 1;
    q.push(pr(0, now));
    while (! q.empty())
    {
        x = q.top().second; q.pop();
        vis[x] = 0;
        if (tag[x] && x != now) return (void)(yhm = min(yhm, dis[x]));
        for (i = head[x]; i; i = nex[i])
        {
            y = ver[i];
            if (dis[y] > dis[x] + len[i])
            {
                dis[y] = dis[x] + len[i];
                if (! vis[y])
                {
                    vis[y] = 1;
                    q.push(pr(dis[y], y));
                }
            }
        }
    }
    return;
}

signed main()
{
    int i, x, y, z;
    n = read(), m = read(), k = read();
    
    for (i = 1; i <= m; ++ i)
    {
        x = read(), y = read(), z = read();
        add_edge(x, y, z);
        add_edge(y, x, z);
    }
    
    for (i = 1; i <= k; ++ i) c[i] = read(), tag[c[i]] = 1;
    
    for (x = 1; x <= k; ++ x) dij(c[x]);
    
    put(yhm);
    return 0;
}

正解：二进制拆分

考虑两个点集S1和S2之间的最短路，我们可以跑一次最短路求出来。

具体可以新建虚拟源点s和虚拟汇点t，s和S1的每个点之间连一条零边，t同理。

那么这一次最短路就相当与求出了|S1|×|S2|对关系之间的最短路最小值。

还可以继续优化

通过二进制分组，我们完全可以使复杂度优化到\(O(m\times logm\times logn)\)

枚举顶点标号的二进制的每一位，如果这一位为1，那么把这个点分到S1，否则分到S2。

为什么不能是只跑一位？因为只跑一位可能会少一些情况，在二进制下，很神奇的就不会漏下情况

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

typedef pair<int, int> pr;

const int N = 2e5 + 66;

priority_queue<pr, vector<pr>, greater<pr> >q;
int n, m, k, res = 123456789;
int g[N];
int dis[N], vis[N];

inline void fuck(int now)
{
    int i, x, y;
    for (i = 1; i <= n; ++ i) dis[i] = 1e9, vis[i] = false;
    for (i = 1; i <= k; ++ i)
    {
        if ((g[i] >> now) & 1)
        {
            q.push(pr(0, g[i]));
            dis[g[i]] = 0;
            vis[g[i]] = 1;
        }
    }
    
    while (! q.empty())
    {
        x = q.top().second; q.pop();
        vis[x] = 0;
        for (i = head[x]; i; i = nex[i])
        {
            y = to[i];
            if (dis[y] > dis[x] + len[i])
            {
                dis[y] = dis[x] + len[i];
                if (! vis[y])
                { 
                    vis[y] = 1;
                    q.push(pr(dis[y], y));
                }
            }
        }
    }
    
    for (i = 1; i <= k; ++ i)
    {
        if (! ((g[i] >> now) & 1))
        {
            res = min(res, dis[g[i]]);
        }
    }
    return;
}

signed main()
{
    int i, x, y, z;
    
    n = read(), m = read(), k = read();
    for (i = 1; i <= m; ++ i)
    {
        x = read(), y = read(), z = read();
        add_edge(x, y, z);
        add_edge(y, x, z);
    }
    for (i = 1; i <= k; ++ i) g[i] = read();
    for (i = 0; i <= 16; ++ i) fuck(i);
    
    put(res);
    return 0;
}