洛谷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;
}