解题思路

• 将状态扩展为分层图：层编号为已使用好石次数 $c\in[0,k]$，状态为 $(v,c)$。

• 转移分两类（设到达点为 $v$，边基础代价为 $w$）：

  • 不用好石：层内转移 $(u,c)\to(v,c)$，代价 $w+\max(a_v,0)$（坏石必加、好石不加）。
  • 用好石（仅当 $a_v<0$ 且 $c<k$）：跨层 $(u,c)\to(v,c+1)$，代价 $w+a_v$（可能为负）。

• 由于层内边权均为非负（至少 $w\ge 1$），可用 $k+1$ 次 Dijkstra 的分层松弛套路：

  • 先在 $c=0$ 层，设 $d_0[1]=0$ 其余为无穷，跑一次 Dijkstra（仅用层内转移，代价 $w+\max(a_v,0)$）。

  • 对每个 $c=0,1,\dots,k-1$：

    • 从所有 $(u,c)$ 通过一次“用好石”的跨层边，生成 $c+1$ 层的多源初始距离：$d_{c+1}[v]\gets \min(d_{c+1}[v],d_c[u]+w+a_v)$（仅当 $a_v<0$）。
    • 以这些初值为源，在 $c+1$ 层再跑一次 Dijkstra（仍只用层内边 $w+\max(a_v,0)$）完成传递。

• 答案为 $\min_{0\le c\le k} d_c[n]$，若皆为无穷则输出 NO。

正确性简述

• 固定好石使用次数 $c$ 后，剩余路径均为非负边，可用 Dijkstra 正确求得该层最短路。
• 从层 $c$ 到层 $c+1$ 的“多源”跨层初始化，枚举了“恰在某次到达时使用第 $c+1$ 次好石”的所有可能，随后在层内 Dijkstra 覆盖使用完第 $c+1$ 次好石后的任意不使用好石的延伸。
• 逐层推进至 $k$，覆盖了所有“至多 $k$ 次”使用好石的路径，取最小值即为全局最优。

C++

#include <bits/stdc++.h>
using namespace std;

static const long long INF = (long long)4e18;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m, k;
	if (!(cin >> n >> m >> k)) return 0;
	vector<long long> a(n + 1);
	for (int i = 1; i <= n; ++i) cin >> a[i];

	vector<vector<pair<int,int>>> g(n + 1);
	for (int i = 0; i < m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}

	// 层内边的“到达点附加代价”：坏石必加a[v]，好石不加（即0）
	vector<long long> addStay(n + 1);
	for (int v = 1; v <= n; ++v) addStay[v] = max(0LL, a[v]);

	auto dijkstra_layer = [&](vector<long long> &dist) {
		// 在当前层，仅允许使用“不用好石”的转移：u->v 代价 w + addStay[v]
		priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
		vector<char> vis(n + 1, 0);
		for (int i = 1; i <= n; ++i) if (dist[i] < INF) pq.push({dist[i], i});
		while (!pq.empty()) {
			auto [du, u] = pq.top(); pq.pop();
			if (vis[u]) continue;
			vis[u] = 1;
			for (auto [v, w] : g[u]) {
				long long nd = du + (long long)w + addStay[v];
				if (nd < dist[v]) {
					dist[v] = nd;
					pq.push({nd, v});
				}
			}
		}
	};

	// c=0 层：从1出发，不用好石
	vector<long long> cur(n + 1, INF);
	cur[1] = 0;
	dijkstra_layer(cur);

	long long ans = cur[n];

	for (int used = 0; used < k; ++used) {
		// 通过一次“用好石”的跨层边，生成下一层的多源初值
		vector<long long> nxt(n + 1, INF);
		for (int u = 1; u <= n; ++u) {
			if (cur[u] >= INF) continue;
			for (auto [v, w] : g[u]) {
				if (a[v] < 0) {
					long long nd = cur[u] + (long long)w + a[v]; // 使用好石（可能为负）
					if (nd < nxt[v]) nxt[v] = nd;
				}
			}
		}
		// 在下一层内跑 Dijkstra（此后不再用好石）
		dijkstra_layer(nxt);
		ans = min(ans, nxt[n]);
		cur.swap(nxt);
	}

	if (ans >= INF / 2) {
		cout << "NO\n";
	} else {
		cout << ans << "\n";
	}
	return 0;
}

Python

import sys
import heapq

INF = 4 * 10**18

def dijkstra_layer(g, add_stay, dist):
	# 层内仅使用“不用好石”的转移：u->v 代价 w + add_stay[v]
	n = len(g) - 1
	pq = []
	vis = [False] * (n + 1)
	for i in range(1, n + 1):
		if dist[i] < INF:
			heapq.heappush(pq, (dist[i], i))
	while pq:
		du, u = heapq.heappop(pq)
		if vis[u]:
			continue
		vis[u] = True
		for v, w in g[u]:
			nd = du + w + add_stay[v]
			if nd < dist[v]:
				dist[v] = nd
				heapq.heappush(pq, (nd, v))

def main():
	data = sys.stdin.read().strip().split()
	it = iter(data)
	try:
		n = int(next(it)); m = int(next(it)); k = int(next(it))
	except StopIteration:
		return
	a = [0] * (n + 1)
	for i in range(1, n + 1):
		a[i] = int(next(it))
	g = [[] for _ in range(n + 1)]
	for _ in range(m):
		u = int(next(it)); v = int(next(it)); w = int(next(it))
		g[u].append((v, w))
		g[v].append((u, w))

	add_stay = [0] * (n + 1)
	for v in range(1, n + 1):
		add_stay[v] = max(0, a[v])

	# c=0 层
	cur = [INF] * (n + 1)
	cur[1] = 0
	dijkstra_layer(g, add_stay, cur)
	ans = cur[n]

	for used in range(k):
		# 跨层一次“用好石”的多源初值
		nxt = [INF] * (n + 1)
		for u in range(1, n + 1):
			if cur[u] >= INF:
				continue
			for v, w in g[u]:
				if a[v] < 0:
					nd = cur[u] + w + a[v]
					if nd < nxt[v]:
						nxt[v] = nd
		# 在下一层内跑 Dijkstra
		dijkstra_layer(g, add_stay, nxt)
		ans = min(ans, nxt[n])
		cur = nxt

	if ans >= INF // 2:
		print("NO")
	else:
		print(ans)

if __name__ == "__main__":
	main()

Java

import java.io.*;
import java.util.*;

// 读入加速
class FastScanner {
	private final InputStream in;
	private final byte[] buffer = new byte[1 << 16];
	private int ptr = 0, len = 0;
	FastScanner(InputStream is) { in = is; }
	private int read() throws IOException {
		if (ptr >= len) {
			len = in.read(buffer);
			ptr = 0;
			if (len <= 0) return -1;
		}
		return buffer[ptr++];
	}
	int nextInt() throws IOException {
		int c, sgn = 1, x = 0;
		do c = read(); while (c <= ' ' && c != -1);
		if (c == '-') { sgn = -1; c = read(); }
		while (c > ' ') {
			x = x * 10 + (c - '0');
			c = read();
		}
		return x * sgn;
	}
}

public class Main {
	static final long INF = 4_000_000_000_000_000_000L;

	static void dijkstraLayer(List<int[]>[] g, long[] addStay, long[] dist) {
		int n = g.length - 1;
		boolean[] vis = new boolean[n + 1];
		PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
		for (int i = 1; i <= n; i++) {
			if (dist[i] < INF) pq.add(new long[]{dist[i], i});
		}
		while (!pq.isEmpty()) {
			long[] top = pq.poll();
			long du = top[0];
			int u = (int) top[1];
			if (vis[u]) continue;
			vis[u] = true;
			for (int[] e : g[u]) {
				int v = e[0], w = e[1];
				long nd = du + w + addStay[v];
				if (nd < dist[v]) {
					dist[v] = nd;
					pq.add(new long[]{nd, v});
				}
			}
		}
	}

	public static void main(String[] args) throws Exception {
		FastScanner fs = new FastScanner(System.in);
		int n = fs.nextInt(), m = fs.nextInt(), k = fs.nextInt();
		long[] a = new long[n + 1];
		for (int i = 1; i <= n; i++) a[i] = fs.nextInt();

		List<int[]>[] g = new ArrayList[n + 1];
		for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();
		for (int i = 0; i < m; i++) {
			int u = fs.nextInt(), v = fs.nextInt(), w = fs.nextInt();
			g[u].add(new int[]{v, w});
			g[v].add(new int[]{u, w});
		}

		long[] addStay = new long[n + 1];
		for (int v = 1; v <= n; v++) addStay[v] = Math.max(0L, a[v]);

		long[] cur = new long[n + 1];
		Arrays.fill(cur, INF);
		cur[1] = 0;
		dijkstraLayer(g, addStay, cur);
		long ans = cur[n];

		for (int used = 0; used < k; used++) {
			long[] nxt = new long[n + 1];
			Arrays.fill(nxt, INF);
			for (int u = 1; u <= n; u++) {
				if (cur[u] >= INF) continue;
				for (int[] e : g[u]) {
					int v = e[0], w = e[1];
					if (a[v] < 0) {
						long nd = cur[u] + w + a[v];
						if (nd < nxt[v]) nxt[v] = nd;
					}
				}
			}
			dijkstraLayer(g, addStay, nxt);
			ans = Math.min(ans, nxt[n]);
			cur = nxt;
		}

		if (ans >= INF / 2) System.out.println("NO");
		else System.out.println(ans);
	}
}

题目内容

在一个奇幻王国里，有 $n$ 个城市(编号依次为 $1$ 到 $n$ )和 $m$ 条双向道路，第 $i$ 条道路连接城市 $u_i$ 和 $v_i$ ， 基础通行时间为正整数 $w_i$ 。此外，王国中每个城市都存在 $1$个中枢魔法石，每个魔法石有一个能量值，非负能量值的魔法石称之为「坏魔法石」，负数能量值的魔法石称之为「好魔法石」，坏魔法石会增加通行所需时间，好魔法石会减少通行所需时间(增加和减少的时间即为能量值的多少)，如果好魔法石足够强力，甚至可以实现时间倒流。

坏魔法石将会强制生效，导致基础通行时间增加，无法被控制。

好魔法石可以控制，选择是否生效，但使用好魔法石的总次数存在限制，第 $k$ 次使用好魔法石生效以后，之后将无法利用任何城市的好魔法石来减少通行时间。换句话说，单次行程中好法石总使用次数不超过 $k$ 次。

魔法石不会消失，可以多次使用。

当你从城市 $u$ 前往城市 $v$ 时，路径的实际通行时间计算如下：

通行时间=城市 $u$ 到城市 $v$ 的道路基础通行时间加上城市 $v$ 生效的魔法石能量值。

请计算从城市 $1$ 到城市 $n$ 的最小实际通行时间，注意，您可以重复经过城市和道路。特别地，如果无论如何都无法到达城市 $n$ ，直接输出 $NO$ 。

输入描述

第一行输入三个整数 $n,m,k(2≤n≤10^3;1≤m≤min${$2×10^3,\frac{n×(n-1)}{2}$}$;1≤k≤10^3)$

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(-10^5 ≤ a_i≤ 10^5)$，其中 $a_i$ 表示第 $i$ 个城市的魔法石能量。

接下来 $m$ 行，第 $i$ 行输入三个整数 $u_i, v_i, w_i(1≤ u_i,v_i≤n;u_i≠v_i;1≤w_i≤10^5)$ ，表示城市 $u_i$ 与城市 $v_i$ 之间存在一条同行时间为 $w_i$ 的路径。除此之外，保证任意两个城市之间至多存在一条道路。

注意，本题不保证图的连通性，即可能存在两个城市之间无法通过任何路径互相到达的情况。

输出描述

如果无论如何都无法到达城市 $n$ ，直接输出下 $NO$ ，否则输出一个整数，表示从城市 $1$ 到城市 $n$ 的最少实际通行时间。

样例1

输入

5 5 2
0 0 0 -10 0
1 2 1
2 3 1
3 5 1
1 4 6
4 5 1

输出

-13

说明

在这个样例中，唯一的最优走法是 $1→2→3→5→4→5→4→5$，实际通行时间为 $1+1+1+(1-10)+1+(1-10)+1$ 。