题解 P8068 【[BalticOI 2002 Day2] Bicriterial routing】

daiarineko · 2022-02-05 18:28:56 · 题解

0. 题意简述

有 m 条双向边，每条有两个权值 c_i,t_i，求两点之间的最短路长度。

本题最短路定义：没有其他同时满足 \sum c_i 和 \sum t_i 都不比它小（当然，如果有两个值都相等的两条路径，只计一次贡献）的路径，则这条路径是一条最短路径。

1. 题目分析&主要代码

考察点：最短路、分层图最短路

题目难度：提高+/省选-

时间复杂度：\Theta(k(n+m)\log (km))，k 为 \sum{c_i}。

题目分析 & 主要代码

这显然是一道最短路题。

相信翻到这篇题解的读者，要么是在练习分层图最短路，~~要么是在做一本通提高篇~~。

这里不再详细讲解分层图本身，而是重点讲解怎么应用到这道题中。（如果你想了解，可以去找分层图模板题的题解）

存储

首先，我们要把分层图压缩成一维存储。

这里使用一个函数 _（使用下划线是为了打起来方便）。

inline int _(int u, int c)
{ //u为原图节点编号，c为层数。
    return c * n + u;
}

由于 u 的取值范围是 [1,n]，范围长度为 n，所以使用 c\times n+u 最为节省空间。

于是可以使用正常前向星存图了。

读入 & 加节点

以下代码中，add(u, v, w) 为前向星模板。

int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &E);
    int p, r, c, t, maxK = 0;
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d%d", &p, &r, &c, &t);
        tmp[i].a = p;
        tmp[i].b = r;
        tmp[i].c = c;
        tmp[i].d = t;
        maxK += c;
    }
    for (int i = 1; i <= m; ++i)
    {
        p = tmp[i].a;
        r = tmp[i].b;
        c = tmp[i].c;
        t = tmp[i].d;
        for (int j = 0; j <= maxK; ++j)
        {
            add(_(p, j), _(r, j + c), t);
            add(_(r, j), _(p, j + c), t);
        }
    }
    ... //省略
}

采取离线读入，第一次读入不处理，目的是获取 \sum c_i（存储到 maxK 变量中）。

Q. 为什么要获取 \sum c_i？
A. 考虑极端情况，所有边连成一条链，此时路径的 \sum c_i 即为全局的 \sum c_i 即 maxK。此时，分层图的层数即为 maxK。

这两行中，由于此条双向边的权值 c_i 为 c，所以此边跨越 c 层，即从第 j 层跨越到第 j + c 层。

            add(_(p, j), _(r, j + c), t);
            add(_(r, j), _(p, j + c), t);

跑最短路

由于全为正权，可以使用 Dijkstra 或 SPFA 算法。

这里使用 Dijkstra 堆优化。

这一部分写模板即可。

统计答案

考虑枚举 \sum c_i。

具体解释：枚举每个 \sum c_i 的路径中 \sum t_i 最小的一个（已经求出）（也就是终点在每一层的节点 e 上的最短路）。

从小到大枚举，同时维护至今为止的 \max \sum t_i，记为 T。

如果 \sum t_i\ge T，就说明之前枚举到了两个权值都不比当前路径大的一条路径，因此当前路径不计入答案。

    int ans = 0, mn = 0x3f3f3fff;
    for (int i = 0; i <= maxK; ++i)
    {
        bool isAns = true;
        if (dis[_(E, i)] >= 0x3f3f3f00 || dis[_(E, i)] >= mn)
            isAns = false;
        mn = min(mn, dis[_(E, i)]);
        if (isAns)
        {
            ++ans;
        }
    }

2. 完整代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 104, maxm = 304, maxk = 104 * maxm;
struct Temp
{
    int a, b, c, d;
} tmp[maxm];
struct Edge
{
    int v, w, next;
} e[maxm * maxk * 2];
int head[maxn * maxk], cnt;
int n, m, s, E;
int dis[maxn * maxk];

inline int _(int u, int c)
{
    return c * n + u;
}
void add(int u, int v, int w)
{
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}
void dij()
{
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    dis[_(s, 0)] = 0;
    q.push({0, _(s, 0)});
    while (!q.empty())
    {
        auto t = q.top();
        q.pop();
        int u = t.second;
        if (dis[u] < t.first)
            continue;
        for (int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].v;
            if (dis[v] > dis[u] + e[i].w)
            {
                dis[v] = dis[u] + e[i].w;
                q.push({dis[v], v});
            }
        }
    }
    return;
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &E);
    int p, r, c, t, maxK = 0;
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d%d", &p, &r, &c, &t);
        tmp[i].a = p;
        tmp[i].b = r;
        tmp[i].c = c;
        tmp[i].d = t;
        maxK += c;
    }
    for (int i = 1; i <= m; ++i)
    {
        p = tmp[i].a;
        r = tmp[i].b;
        c = tmp[i].c;
        t = tmp[i].d;
        for (int j = 0; j <= maxK; ++j)
        {
            add(_(p, j), _(r, j + c), t);
            add(_(r, j), _(p, j + c), t);
        }
    }
    dij();
    int ans = 0, mn = 0x3f3f3fff;
    for (int i = 0; i <= maxK; ++i)
    {
        bool isAns = true;
        if (dis[_(E, i)] >= 0x3f3f3f00 || dis[_(E, i)] >= mn)
            isAns = false;
        mn = min(mn, dis[_(E, i)]);
        if (isAns)
        {
            ++ans;
        }
    }
    printf("%d\n", ans);
    return 0;
}

3. Note

本解法时间复杂度较高，需要 O2 优化才能通过此题。此题可能有更优解法。
注意细节：双向边、非严格单调（含取等情况）。
注意开两倍数组，经试验正好能卡进空间限制。
抄题解是不好的习惯。