洛谷P9659 [ICPC2021 Macao R] Shortest Path Fast Algorithm 题解

题目链接：P9659 [ICPC2021 Macao R] Shortest Path Fast Algorithm

题意：

最近，cxy 学习了最短路径快速算法（SPFA，或更正式地说，贝尔曼–福特–摩尔算法）以有效地解决最短路径问题。她意识到，如果用优先队列代替先进先出队列，该算法看起来与 Dijkstra 算法非常相似，并向你展示了下面的伪代码。

「选择 $Q$ 中最佳顶点」表示选择具有最小 priority 值的顶点（如果有多个顶点具有最小 priority 值，则选择其中索引最大的顶点）。

作为未来的计算机科学家，你发现 cxy 修改后的 SPFA 算法在某些精心构造的图中运行速度非常慢。然而，cxy 确信她的算法很好，除非你向她展示一个简单的无向图，在该图中，SPFA 函数中的变量 $\tt{cnt}$ 在某个时刻不少于某个 $k$。为方便起见，SPFA 函数的源顶点被指定为顶点 $1$。

就给她个教训吧！

输入格式：

每个测试文件中只有一个测试用例。

输入的第一行包含一个整数 $k$，其中 $k = 1$ 为示例测试用例，$k = 10^5$ 为唯一的隐藏测试用例。

输出格式：

输出几行以以下格式描述简单无向图的输入数据，使得 SPFA 函数中的变量 $\tt{cnt}$ 在某个时刻不少于 $k$。

第一行包含两个整数 $n$（$1 \le n \le 100$）和 $m$（$0 \le m \le 10^3$），表示图中的顶点数和边数。

然后，跟着 $m$ 行，第 $i$ 行包含三个整数 $u_i$、$v_i$（$1 \le u_i, v_i \le n$）和 $w_i$（$1 \le w_i \le 10^6$），表示图中的第 $i$ 条边的权重为 $w_i$，连接了第 $u_i$ 个和第 $v_i$ 个顶点。

注意，简单图不包含自环和重边。

提示说明

附件：spfa.cpp

为方便起见，你可以从比赛网站上复制与给定伪代码对应的 C++ 代码。将代码保存为 spfa.cpp，使用 g++ spfa.cpp -O2 -o spfa 进行编译，你将得到一个名为 spfa 的可执行文件。运行 spfa，将你的输出提供给它的标准输入，它将打印出 $\tt{cnt}$ 的最终值。

给出示例输出后，它将打印出 $4$，这意味着示例输出不足以通过隐藏测试用例。

注意，给定的代码不会检查你的输出的有效性（例如，它不会检查你的输出是否真的是一个简单图）。即使可执行文件打印出一个很大的值，如果你的输出无效，你仍然可能失败测试。

显然每个点入队后，这个点在优先队列中的 priority 值直到它出队时都不会变化

那么很有可能有 priority 值特别大的一直卡在优先队列里面出不来。

考虑利用这个性质。记 $v_1,v_2$ 为极大值且 $v_1 > 2v_2$ ，构造下图。

在这种情况下，出队的顺序为 $1,3,4,2,4$ ，其中 $4$ 会出队两次。

那么我们以 $4$ 为起点再次构造这样的结构，cnt 的值可由以下递推式得到

$f(3k+1) = 5 + 2f(3k-2)$

其中 $k$ 为结构的总数，$f(1)=1$ 。

解一下递推式

$\begin{aligned} f(3k+1) &= 5 + 2(5 + 2(\cdots)) \\[6pt] &= 2^k + 5\times 2^{k-1} + \cdots \\[6pt] &= 2^k + 5\times (2 ^k - 1) \\[6pt] &= 6\times 2^k - 5 \end{aligned}$

取个 $k=16$ 即可。注意构造的时候 $v_3,v_4$ 要比 $v_1,v_2$ 小。

时间复杂度 $\mathcal{O}(1)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)())

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << 100 << ' ' << 16 * 5 << '\n';
    int last = 1, now = 1e6;
    rep(i, 1, 16)
    {
        const int a = last, b = a + 1, c = b + 1, d = c + 1;
        --now;
        cout << a << ' ' << b << ' ' << now << '\n';
        now >>= 1; now -= 5;
        cout << a << ' ' << c << ' ' << 1 << '\n';
        cout << c << ' ' << b << ' ' << 1 << '\n';
        cout << c << ' ' << d << ' ' << now << '\n';
        cout << b << ' ' << d << ' ' << 1 << '\n';
        last = d;
    }
    return 0;
}