题解：P3547 [POI 2013] CEN-Price List

· · 题解

题目链接：P3547 [POI 2013] CEN-Price List

:::info[推导过程]

首先，读完题我们可以发现这道题可以转换为在原图的铁路边和满足条件的飞机边构成的新图中，求从 k 出发到所有点的最短路。

而我们容易发现，最短路径由以下三种情况构成：

对于前面两种情况，我们只需要在原图上用 BFS 跑一遍最短路。容易发现如果使用飞机边那么肯定代表相邻两条铁路边的花费大于飞机边的花费，为了使花费最少，我们应当尽可能使用飞机边。所以前两种情况只需要跑一遍最短路，然后对于每个点 i 到 k 的最短路径，考虑使用或者不使用飞机边两种情况的花费取最小值即可。比较好解决。具体实现请看代码，自认为代码实现易懂。

但对于第三种情况，如果直接枚举每个点的所有两步路径来建飞机边，显然复杂度可能达到 O(m^2)，在这道题中无法接受。因此我们考虑如何优化，也就是如何在不显式建立飞机图的情况下，求出只使用飞机边时的最短路。

对于不优化的情况，我们仍然需要在图上跑 BFS。我们观察到 BFS 有一个很重要的性质：当一个点第一次被访问时，此时得到的就是它在飞机图中的最短距离。这个性质很显然，就不再证明了。于是我们可以思考从这个性质入手，看如何优化。

具体地，我们假设当前正在处理点 x，它的飞机邻居 z 是通过：

x \to y \to z

找到的。

那么：

dist_z = dist_x + 1

如果之后又从另一个点 x' 找到了 z，由于 BFS 按照距离递增的顺序处理队列，所以：

dist_{x'} \ge dist_x

因此：

dist_{x'} + 1 \ge dist_x + 1

也就是说，第二次找到 z 不可能让它的距离变得更优。

既然以后再也不需要通过新的起点更新 z，那么我们就可以考虑删除刚才用于找到 z 的那条第二层枚举边。但是我们发现好像不太好分析这个操作具体能使复杂度优化成多少。

题目中定义我们枚举路径 x \to y \to z，只有原图中不存在 x \to z 的边我们才考虑采用飞机边。换言之，如果存在 x \to z 的边，我们绝对不可以删除我们上文所说的用于找到 z 的那条第二层枚举边。

对于这种不成立的情况，我们可以观察到 x,y,z 三点构成了一个三元环。于是我们现在把这道题和三元环联系起来了。形成三元环的条件下，不能删除第二条边，因此边可能被重复枚举。

但通过对于三元环计数的模板题：P1989这道题的学习，我们可以发现一个性质：在一个简单无向图中，三元环的数量不会超过 O(m \sqrt{m})。这个结论是怎么得来的呢？其实也很显然。

按照三元环计数中的思想，我们把所有边按照度数从小到大定向，度数相同按照编号从小到大定向。这样我们可以保证每个点的出度不超过 O(\sqrt{m})。因为：

对于一张无向图，每条无向边都会给两个端点各贡献一次度数，所以每条边贡献 2。

因此：

\sum_{i=1}^{n} deg(i) = 2m

综上，一张无向图中所有点的出度不超过 O(\sqrt{m})。

于是枚举一条边，再枚举端点的出边，复杂度就是 O(m\sqrt m)。

我们发现这个复杂度我们是可以接受的，于是这道题就这样解决了。

:::

:::info[复杂度分析]{open}

因此总时间复杂度为：O(n+m\sqrt{m})。

空间复杂度为 O(n+m)。

可以通过这道题。

:::success[参考代码]

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 1e5 + 10;
const int M = 1e5 + 10;

int n, m, k, a, b;

int head[N], idx;
int head2[N], idx2;

struct node
{
    int to, nxt;
}e[M << 1], e2[M << 1];

int dist[N], flag[N];
bool vis[N];
ll ans[N];

inline void add(int u, int v)
{
    e[idx].to = v;
    e[idx].nxt = head[u];
    head[u] = idx++;
}

inline void add2(int u, int v)
{
    e2[idx2].to = v;
    e2[idx2].nxt = head2[u];
    head2[u] = idx2++;
}

inline void bfs1()
{
    queue <int> q; q.push(k); dist[k] = 0; vis[k] = true;

    while (!q.empty())
    {
        auto u = q.front(); q.pop();

        for (int i = head[u]; ~i; i = e[i].nxt)
        {
            int v = e[i].to;
            if (vis[v]) continue;
            dist[v] = dist[u] + 1;
            vis[v] = true;
            q.push(v);
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        ans[i] = min((ll)dist[i] * a, (ll)dist[i] / 2 * b + (ll)dist[i] % 2 * a);
    }
}

inline void bfs2()
{
    memset(vis, false, sizeof vis);
    memset(dist, 0, sizeof dist);
    queue <int> q; q.push(k); vis[k] = true;

    while (!q.empty())
    {
        auto u = q.front(); q.pop();

        for (int i = head[u]; ~i; i = e[i].nxt)   
        {
            int v = e[i].to;
            flag[v] = u;
        }

        for (int i = head[u]; ~i; i = e[i].nxt)
        {
            int v = e[i].to;
            int pre = -1;

            for (int j = head2[v]; ~j; j = e2[j].nxt)
            {
                int z = e2[j].to;

                if (flag[z] != u)
                {
                    if (pre == -1) head2[v] = e2[j].nxt;
                    else e2[pre].nxt = e2[j].nxt;

                    if (vis[z]) continue;

                    dist[z] = dist[u] + 1;
                    q.push(z);
                    vis[z] = true;
                }
                else pre = j;
            }
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        if (!vis[i]) continue;
        ans[i] = min(ans[i], (ll)dist[i] * b);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> k >> a >> b;

    memset(head, -1, sizeof head);
    memset(head2, -1, sizeof head2);

    for (int i = 1; i <= m; ++i)
    {
        int u, v; cin >> u >> v;
        add(u, v); add(v, u);
        add2(u, v); add2(v, u);
    }

    bfs1(); bfs2();

    for (int i = 1; i <= n; ++i) cout << ans[i] << endl;

    return 0;
}

:::