题解 | #魔法路径#

题目链接

魔法路径

题目描述

在一个有 $N$ 个城市和 $M$ 条双向道路的王国中，计算从城市 1 到城市 $N$ 的最小通行时间。

每条道路连接城市 $u$ 和 $v$ ，基础通行时间为 $w$ 。
每个城市 $i$ 有一个魔法石，能量值为 $a_i$ 。
坏魔法石 ( $a_i \ge 0$ )：强制生效，增加通行时间。
好魔法石 ( $a_i < 0$ )：可以选择是否生效来减少通行时间。
限制：在单次行程中，好魔法石的使用总次数不能超过 $K$ 次。
城市和道路可以重复经过。如果无法到达，输出 NO。

解题思路

本题是一个带有负权边的状态最短路问题。由于 SPFA 算法在某些数据下会超时，最高效稳妥的解法是分层图最短路。

状态定义： $dist[i][j]$ 表示到达城市 $i$ ，至多使用了 $j$ 次好魔法石所花费的最小时间。
分层计算：我们按 $k$ (已用次数) 从 0 到 $K$ 的顺序，逐层计算最短路径。
1. 继承：为了满足“至多” $j$ 次的定义，在计算第 $k$ 层前，我们先让它继承第 $k-1$ 层的最优解：dist[i][k] = dist[i][k-1]。
2. 层内移动 (Dijkstra)：在同一层 $k$ 内，从 $u$ 到 $v$ 的移动不增加好魔法石使用次数。成本为 w + max(0, a[v]) (路费 + 目的地 v 的坏魔法石惩罚)。此成本非负，可在该层内安全地使用 Dijkstra 算法更新最短路。
3. 层间转移：当我们算完第 $k$ 层的最短路后，就可以用它来更新第 $k+1$ 层。如果从 $u$ （在第 $k$ 层）移动到 $v$ ，且 $v$ 有好魔法石（ $a_v < 0$ ），我们可以选择使用它，这就构成了一次到 $k+1$ 层的转移。dist[v][k+1] 可以由 dist[u][k] + w + a[v] 更新。

算法流程：

初始化 $dist$ 数组为无穷大， $dist[1][0] = 0$ 。
循环 $k$ 从 0 到 $K-1$ ： a. 继承：dist[i][k+1] = dist[i][k]。 b. 层内 Dijkstra：在第 $k$ 层上运行 Dijkstra 算法。 c. 层间转移：用第 $k$ 层的结果去更新第 $k+1$ 层的距离。
在计算完所有层后，对最后一层 $K$ 再运行一次 Dijkstra，以确保层内的最优解被充分传播。
最终答案是 $dist[N][K]$ 。

代码

c++
java
python

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

using namespace std;

const long long INF = 1e18; 

void dijkstra(int n, int k_level, vector<vector<long long>>& dist, const vector<long long>& a, const vector<vector<pair<int, int>>>& adj) {
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    for (int i = 1; i <= n; ++i) {
        if (dist[i][k_level] != INF) {
            pq.push({dist[i][k_level], i});
        }
    }

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u][k_level]) {
            continue;
        }

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            long long cost = w + (a[v] >= 0 ? a[v] : 0);
            if (dist[u][k_level] != INF && dist[u][k_level] + cost < dist[v][k_level]) {
                dist[v][k_level] = dist[u][k_level] + cost;
                pq.push({dist[v][k_level], v});
            }
        }
    }
}

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

    int n, m, k;
    cin >> n >> m >> k;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    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<vector<long long>> dist(n + 1, vector<long long>(k + 1, INF));
    dist[1][0] = 0;
    
    dijkstra(n, 0, dist, a, adj);

    for (int k_used = 0; k_used < k; ++k_used) {
        // 继承
        for(int i = 1; i <= n; ++i) {
            dist[i][k_used + 1] = dist[i][k_used];
        }

        // 转移
        for (int u = 1; u <= n; ++u) {
            if (dist[u][k_used] != INF) {
                for (auto& edge : adj[u]) {
                    int v = edge.first;
                    int w = edge.second;
                    if (a[v] < 0) {
                        dist[v][k_used + 1] = min(dist[v][k_used + 1], dist[u][k_used] + w + a[v]);
                    }
                }
            }
        }
        
        // Dijkstra on new level
        dijkstra(n, k_used + 1, dist, a, adj);
    }

    long long min_dist = dist[n][k];

    if (min_dist == INF) {
        cout << "NO\n";
    } else {
        cout << min_dist << '\n';
    }

    return 0;
}

import java.util.*;

public class Main {
    static class State implements Comparable<State> {
        long time;
        int city;

        State(long time, int city) {
            this.time = time;
            this.city = city;
        }

        @Override
        public int compareTo(State other) {
            return Long.compare(this.time, other.time);
        }
    }

    static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
    
    private static void dijkstra(int n, int kLevel, long[][] dist, long[] a, List<List<Edge>> adj) {
        PriorityQueue<State> pq = new PriorityQueue<>();
        for (int i = 1; i <= n; i++) {
            if (dist[i][kLevel] != Long.MAX_VALUE) {
                pq.add(new State(dist[i][kLevel], i));
            }
        }

        while (!pq.isEmpty()) {
            State current = pq.poll();
            long d = current.time;
            int u = current.city;

            if (d > dist[u][kLevel]) {
                continue;
            }

            for (Edge edge : adj.get(u)) {
                int v = edge.to;
                int w = edge.weight;
                long cost = w + (a[v] >= 0 ? a[v] : 0);
                if (dist[u][kLevel] != Long.MAX_VALUE && dist[u][kLevel] + cost < dist[v][kLevel]) {
                    dist[v][kLevel] = dist[u][kLevel] + cost;
                    pq.add(new State(dist[v][kLevel], v));
                }
            }
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();

        long[] a = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextLong();
        }

        List<List<Edge>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            adj.get(u).add(new Edge(v, w));
            adj.get(v).add(new Edge(u, w));
        }

        long[][] dist = new long[n + 1][k + 1];
        for (long[] row : dist) {
            Arrays.fill(row, Long.MAX_VALUE);
        }
        dist[1][0] = 0;
        
        dijkstra(n, 0, dist, a, adj);

        for (int kUsed = 0; kUsed < k; kUsed++) {
            // 继承
            for(int i = 1; i <= n; i++) {
                dist[i][kUsed + 1] = dist[i][kUsed];
            }
            
            // 转移
            for (int u = 1; u <= n; u++) {
                if (dist[u][kUsed] != Long.MAX_VALUE) {
                    for (Edge edge : adj.get(u)) {
                        int v = edge.to;
                        int w = edge.weight;
                        if (a[v] < 0) {
                            dist[v][kUsed + 1] = Math.min(dist[v][kUsed + 1], dist[u][kUsed] + w + a[v]);
                        }
                    }
                }
            }
            
            dijkstra(n, kUsed + 1, dist, a, adj);
        }


        long minDist = dist[n][k];

        if (minDist == Long.MAX_VALUE) {
            System.out.println("NO");
        } else {
            System.out.println(minDist);
        }
    }
}

import heapq
import collections

def dijkstra(n, k_level, dist, a, adj):
    pq = []
    for i in range(1, n + 1):
        if dist[i][k_level] != float('inf'):
            heapq.heappush(pq, (dist[i][k_level], i))
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if d > dist[u][k_level]:
            continue
        
        for v, w in adj[u]:
            cost = w + (a[v] if a[v] >= 0 else 0)
            if dist[u][k_level] != float('inf') and dist[u][k_level] + cost < dist[v][k_level]:
                dist[v][k_level] = dist[u][k_level] + cost
                heapq.heappush(pq, (dist[v][k_level], v))

def solve():
    n, m, k = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    
    adj = collections.defaultdict(list)
    for _ in range(m):
        u, v, w = map(int, input().split())
        adj[u].append((v, w))
        adj[v].append((u, w))
        
    inf = float('inf')
    dist = [[inf] * (k + 1) for _ in range(n + 1)]
    dist[1][0] = 0
    
    dijkstra(n, 0, dist, a, adj)
    
    for k_used in range(k):
        # 继承
        for i in range(1, n + 1):
            dist[i][k_used + 1] = dist[i][k_used]
        
        # 转移
        for u in range(1, n + 1):
            if dist[u][k_used] != inf:
                for v, w in adj[u]:
                    if a[v] < 0:
                        dist[v][k_used + 1] = min(dist[v][k_used + 1], dist[u][k_used] + w + a[v])

        dijkstra(n, k_used + 1, dist, a, adj)
                            
    min_dist = dist[n][k]
    
    if min_dist == inf:
        print("NO")
    else:
        print(min_dist)

solve()

算法及复杂度

算法：分层图最短路。该算法通过将“使用好魔法石的次数”作为分层标准，将原问题分解为 $K+1$ 个阶段。在每个阶段内部，由于边权非负（层内移动），可以使用高效的 Dijkstra 算法求解。
时间复杂度：外层循环执行 $K$ 次，每次循环的核心是一次 Dijkstra 算法。Dijkstra 的复杂度为 $\mathcal{O}(M \log N)$ 。因此，总时间复杂度为 $\mathcal{O}(K \cdot M \log N)$ 。
空间复杂度：主要由邻接表和 $dist$ 数组决定。邻接表需要 $\mathcal{O}(N+M)$ 的空间， $dist$ 数组需要 $\mathcal{O}(N \cdot (K+1))$ 的空间。因此，总空间复杂度为 $\mathcal{O}(N \cdot K + M)$ 。