G. Bicycles - 题解

比赛与标签

比赛: Codeforces Round 918 (Div. 4) 标签: graphs, greedy, implementation, shortest paths, sortings 难度: *1800

题目大意喵~

各位骑士大人，下午好喵~！这次我们要帮助可怜的 Slavic 解决一个旅行难题呐。

事情是这样的：在一个由 $n$ 个城市和 $m$ 条道路构成的世界里，Slavic 要从城市 1 出发，去城市 $n$ 参加一个盛大的派对！每条路连接两个城市，并且有一个固定的长度 $w_i$ 。

问题来了，Slavic 没有自行车，但他很有钱！每个城市 $i$ 都恰好有一辆自行车出售，这辆自行车的“迟缓度”是 $s_i$ 。当 Slavic 使用一辆迟缓度为 $s_j$ 的自行车通过一条长度为 $w_i$ 的路时，花费的时间是 $w_i \cdot s_j$ 。

Slavic 可以在任何他到达的城市购买自行车，而且可以拥有很多辆。因为他想快点到派对，所以每次骑行，他都会选择自己拥有的所有自行车中迟缓度最低（也就是速度最快）的那一辆。

我们的任务就是，计算出 Slavic 从城市 1 到达城市 $n$ 所需要的最短时间是多少呢？喵~

解题思路分析呐！

这道题第一眼看上去，不就是个经典的最短路问题嘛！但是呢，事情没有那么简单喵。路上的花费（边权）不是固定的，它取决于我们当时骑的是哪辆自行车。这就让普通的 Dijkstra 或者 SPFA 算法有点头疼了。

不过别担心，我们猫娘有特殊的解题技巧！当普通的状态（比如只记录当前位置）不足以描述问题时，我们就给它“升维”！

核心思路是，影响我们决策的，除了当前在哪座城市，还有我们手上最好的自行车是哪一辆（也就是最小的那个迟缓度）。只要确定了这两点，我们就可以做出最优的下一步决策了。

所以，我们可以定义一个新的状态：(当前城市 u, 当前拥有的最小迟缓度 b)。我们的目标就变成了，找到到达任何 (城市 n, 任意迟缓度 b) 这个状态的最小时间。

这样一来，问题就转化成了一个在“状态图”上的最短路问题啦！

状态图的节点: (u, b)，表示身处城市 u，拥有的最好自行车的迟缓度为 b。
状态图的边 (状态转移): 假设我们当前处于状态 (v, b)，时间花费为 d。
1. 我们首先到达了城市 v。这时，我们可以选择购买城市 v 的自行车，它的迟缓度是 s[v]。那么我们手上最好的自行车迟缓度就会更新为 new_b = min(b, s[v])。这是个贪心选择，因为我们总想用最快的车嘛！
2. 然后，我们从城市 v 出发，前往它的一个邻居城市 u，它们之间的道路长度为 w。我们会用手上最好的车，也就是迟缓度为 new_b 的那辆。
3. 这次旅行花费的时间是 w * new_b。
4. 到达城市 u 后，我们的新状态就是 (u, new_b)，总时间是 d + w * new_b。

这样，我们就可以用一个类似 Dijkstra 或 SPFA 的算法来求解了。我们可以创建一个二维的 dist 数组，dist[u][b] 记录到达状态 (u, b) 的最短时间。

算法步骤如下喵:

创建一个二维数组 dist[N][S_max]，初始化为无穷大。N是城市数量，S_max是最大迟缓度（这里是1000）。
Slavic 从城市 1 出发，他必须先买下城市 1 的自行车。所以，初始状态是 (城市 1, 迟缓度 s[1])，花费时间为 0。即 dist[1][s[1]] = 0。
将初始状态 (时间=0, 城市=1, 迟缓度=s[1]) 推入一个队列中（AC代码用了普通队列，类似SPFA；用优先队列实现Dijkstra也是完全可以的）。
当队列不为空时，取出一个状态 (d_v, v, b)。
对于城市 v 的每一个邻居 u（道路长度为 w）：
- 首先更新我们拥有的最好自行车：new_b = min(b, s[v])。
- 计算到达邻居 u 的新时间：d_u = d_v + w * new_b。
- 如果 d_u < dist[u][new_b]，说明我们找到了一条更短的路径到达状态 (u, new_b)。更新 dist[u][new_b] = d_u，并将新状态 (d_u, u, new_b) 推入队列。
算法结束后，我们想知道到达城市 n 的最短时间。因为我们可能带着任何迟缓度的自行车到达终点，所以最终答案就是 min(dist[n][b])，其中 b 的范围是 1 到 1000。

这样，一个复杂的问题就被我们巧妙地转化解决了，是不是很厉害呀，喵~

代码实现喵~

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
#include <tuple>

using namespace std;
using ll = long long; // 路程花费可能会很大，用 long long 才保险喵

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;

        // 用邻接表存储图的信息，pair存 {邻居节点, 道路长度}
        vector<vector<pair<int, int>>> adj(n + 1);
        for (int i = 0; i < m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }

        // 存储每个城市自行车的迟缓度
        vector<int> s(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> s[i];
        }

        // dist[i][j] 表示到达城市 i，且拥有的最好自行车迟缓度为 j 的最短时间
        // 迟缓度最大为 1000，所以第二维开到 1001
        vector<vector<ll>> dist(n + 1, vector<ll>(1001, LLONG_MAX));
        
        // 使用一个普通队列进行类似 BFS/SPFA 的搜索
        // 队列里存三元组: {当前城市, 当前最小迟缓度, 到达当前状态的总时间}
        queue<tuple<int, int, ll>> q;

        // 初始状态：在城市1，必须买下当地的自行车，时间为0
        dist[1][s[1]] = 0;
        q.push({1, s[1], 0});

        while (!q.empty()) {
            // 取出队首状态
            auto [v, b, d_v] = q.front();
            q.pop();

            // 如果当前路径不是最优的，就跳过，这是个常见优化
            if (d_v > dist[v][b]) {
                continue;
            }

            // 在城市 v，可以买下 s[v] 的自行车，更新手上最好的自行车
            int new_b = min(b, s[v]);

            // 遍历所有从 v 出发的边
            for (auto [u, w] : adj[v]) {
                // 用手上最好的自行车（迟缓度为 new_b）去往邻居 u
                ll d_u = d_v + static_cast<ll>(w) * new_b;
                
                // 如果找到了更短的路径到达状态 (u, new_b)
                if (d_u < dist[u][new_b]) {
                    // 更新最短时间并把新状态入队
                    dist[u][new_b] = d_u;
                    q.push({u, new_b, d_u});
                }
            }
        }

        // 遍历所有可能到达终点 n 的状态，找到最小值
        ll ans = LLONG_MAX;
        for (int b = 1; b <= 1000; b++) {
            if (dist[n][b] < ans) {
                ans = dist[n][b];
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析的说

时间复杂度: O((N+M) * S_max) 的说。这里的 N 是城市数，M 是道路数，S_max 是最大迟缓度（1000）。我们的状态总数是 N * S_max。在类似SPFA的算法中，每个状态最多被松弛 deg(v) 次（v是状态中的城市），所以总的计算量大致和状态图的边数成正比。状态图的边数大约是 M * S_max。因此，总时间复杂度是 O((N + M) * S_max)。对于这道题的限制，这个复杂度是可以通过的呐。
空间复杂度: O(N * S_max) 的说。主要的内存开销来自于 dist 数组，它的大小是 N * S_max。邻接表和队列占用的空间相对较小。所以空间复杂度就是 O(N * S_max)。

知识点与总结喵！

这道题真是一次有趣的冒险！它教会了我们几件重要的事情：

状态扩展大法: 当标准算法的“状态”不足以解决问题时（比如这里的边权是动态的），不要害怕！把影响决策的变量（最小迟缓度）加入到状态定义中，构建一个更强大的“状态图”，问题就迎刃而解啦。
图论建模: 本质上，我们是把一个带有动态边权的图问题，转化成了一个在新的、更大的、静态边权的图上的最短路问题。这是解决此类问题的一个非常核心和通用的思想！
贪心选择: 在旅行过程中，我们总是选择当前拥有的最快自行车。这个小小的贪心策略，极大地简化了状态，我们只需要记录最小的 s 值，而不是一个复杂的自行车集合。
注意数据范围: 路径长度 w * s 可能会超过 int 的范围，所以记得要用 long long 来存储距离，不然就会因为溢出而得到错误的答案哦！

希望这篇题解能帮助到你，让你对图论的理解更深一层！继续加油，探索算法的奇妙世界吧，喵~！

G. Bicycles - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路分析呐！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结喵！ ​