Skip to content

P4822 [BJWC2012] 冻结

原题链接：P4822 [BJWC2012] 冻结

Tag：最短路、分层图

题目描述

我们考虑最简单的旅行问题吧： 现在这个大陆上有 \(N\) 个城市，\(M\) 条双向的道路。 城市编号为 \(1\) ~ \(N\)，我们在 \(1\) 号城市，需要到 \(N\) 号城市，怎样才能最快地到达呢？

这不就是最短路问题吗？我们都知道可以用 Dijkstra、Bellman-Ford、Floyd-Warshall等算法来解决。

现在，我们一共有 \(K\) 张可以使时间变慢 \(50\%\) 的 SpellCard，也就是说，在通过某条路径时， 我们可以选择使用一张卡片，这样，我们通过这一条道路的时间 就可以减少到原先的一半。需要注意的是：

  1. 在一条道路上最多只能使用一张 SpellCard。
  2. 使用一张SpellCard 只在一条道路上起作用。
  3. 你不必使用完所有的 SpellCard。

给定以上的信息，你的任务是：求出在可以使用这不超过 \(K\) 张时间减速的 SpellCard 之情形下， 从城市 \(1\) 到城市 \(N\) 最少需要多长时间。

数据说明：

\(1 \leq K \leq N \leq 50\)，\(M \leq 10^3，1 \leq A_i,B_i \leq N\)，\(2 \leq Time_i \leq 2 \times 10^3\)。

分析

首先十分显然这是一道分层图的题。

当我们观察到题目给出一张图， 要求你在图上做出 \(k\) 次决策的时候， 并且每一次决策不改变图的结构，只改变状态/边权时， 只要 \(n * k\) 足够小，我们就可以用分层图来解决。

可以观看 分层图 中， 我们提到的例题，和这道题的思路完全一致， 唯一不同的地方是这个题的决策并不是把边权变为 \(0\)， 而是边权减半。 因此我们只需要在「跨层连边」时， 把这些跨层边的边权设置为 \(w / 2\) 即可。

代码实现

typedef pair<int,int> PII;

void IHaveNoLimitation() {
    int n, m, k;
    cin >> n >> m >> k;
    int s, t;
    s = 1,t = n;
    vector<vector<PII>> adj((k + 1) * n + 5);
    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});
        for (int j = 1; j <= k; ++j) {
            adj[(j - 1) * n + u].push_back({j * n + v, w / 2});
            adj[(j - 1) * n + v].push_back({j * n + u, w / 2});
            adj[j * n + u].push_back({j * n + v, w});
            adj[j * n + v].push_back({j * n + u, w});
        }
    }
    vector<int> dis((k + 1) * n + 5,INT_MAX), vis((k + 1) * n + 5);
    auto dijkstra = [&](int s) {
        dis[s] = 0;
        priority_queue<PII, vector<PII>, greater<PII>> pq;
        pq.push({0, s});
        while (!pq.empty()) {
            auto [w, cur] = pq.top();
            pq.pop();
            if (vis[cur]) continue;
            vis[cur] = 1;
            for (auto &nxt: adj[cur]) {
                auto &[to, val] = nxt;
                if (dis[to] > dis[cur] + val) {
                    dis[to] = dis[cur] + val;
                    pq.push({dis[to], to});
                }
            }
        }
    };
    dijkstra(s);
    int ans = INT_MAX;
    for (int i = 0; i <= k ; i++) {
        ans = min(ans,dis[i * n + t]);
    }
    cout << ans << endl;
}

日志

本页面创建于 2025/12/04 16:23