来源第 508 场周赛 Q4难度困难分数2102
题目描述
给你一个有 n 个节点的 有向 加权图,节点编号从 0 到 n - 1。
该图由一个二维整数数组 edges 表示,其中 edges[i] = [ui, vi, ti] 表示一条从节点 ui 到节点 vi 的有向边,通过该边需要花费 ti 秒。
同时给你一个整数 power 表示初始可用电量,以及一个长度为 n 的整数数组 cost,其中 cost[u] 表示从节点 u 通过 任意 一条 出 边转发信号所需的电量。
给你两个整数 source 和 target。
信号在时间 0 从 source 出发,拥有 power 单位的电量,并遵循以下规则:
- 只有当剩余电量 至少 为
cost[u] 时,信号才能遍历从节点 u 出发的有向边。 - 信号到达一个节点时不消耗任何电量,除非它稍后通过另一条边离开该节点。
- 当信号从节点
u 转发时,剩余电量将 减少 cost[u] 个单位。 - 遍历一条边
edges[i] = [ui, vi, ti] 会使总时间 增加 ti 秒。
返回一个大小为 2 的整数数组 answer,其中:
answer[0] 是信号到达节点 target 所需的 最小 时间。 answer[1] 是所有实现 answer[0] 的路径中 最大 的剩余电量。
如果信号无法到达 target,则返回 [-1, -1]。
示例 1:

输入: n = 5, edges = [[0,1,1],[1,4,1],[0,2,1],[2,3,1],[3,4,1]], power = 4, cost = [2,3,1,1,1], source = 0, target = 4
输出: [3,0]
解释:
- 信号从节点 0 出发,拥有 4 个单位的电量。
- 路径
0 -> 1 -> 4 无效,因为离开节点 0 后,信号剩余 2 个单位的电量,这小于 cost[1] = 3。 - 有效路径
0 -> 2 -> 3 -> 4 总共花费时间为 3。 - 沿着这条路径消耗的总电量为
cost[0] + cost[2] + cost[3] = 4,剩余电量为 0。 - 因此,答案为
[3, 0]。
示例 2:

输入: n = 3, edges = [[0,1,2],[1,2,2],[2,0,2]], power = 3, cost = [1,1,1], source = 1, target = 1
输出: [0,3]
解释:
- 由于
source 和 target 是同一个节点,不需要通过任何节点。 - 因此,花费的最小总时间为 0,并且不消耗电量。
- 因此,答案为
[0, 3]。
示例 3:

输入: n = 4, edges = [[0,1,3],[2,3,4]], power = 3, cost = [1,1,1,1], source = 0, target = 3
输出: [-1,-1]
解释:
没有从 source 到 target 的有效路径,因此返回 [-1, -1]。
提示:
1 <= n <= 1000 0 <= edges.length <= 1000 edges[i] = [ui, vi, ti] 0 <= ui, vi <= n - 1 1 <= ti <= 109 1 <= power <= 1000 cost.length == n 1 <= cost[i] <= 2000 0 <= source, target <= n - 1
解法
方法一:堆优化 Dijkstra
思考
边权是时间,但每个结点还消耗电量,剩余电量必须进入状态。 \(n,\textit{power}\le 1000\),状态数 \(n\times\textit{power}\) 可接受。
\(\textit{dist}[u][p]\) 表示到达 \(u\) 且剩电 \(p\) 的最少时间。堆优化 Dijkstra 弹出 \((d,p,u)\);时间相同则优先剩电更多,以便更早到达目标时保留电量。电量不足 \(\textit{cost}[u]\) 则无法转发。
首次弹出目标即最短时间下的最大剩余电量。
这是一道最短路径问题,但状态中除了当前节点,还需要记录剩余电量。
我们定义 \(\textit{dist}[u][p]\) 表示到达节点 \(u\) 且剩余电量为 \(p\) 时的最少时间。初始时 \(\textit{dist}[\textit{source}][\textit{power}] = 0\),其余状态为正无穷。
使用优先队列进行 Dijkstra 算法,队列中存储三元组 \((d, p, u)\),分别表示当前的最少时间、剩余电量和当前节点。为了在时间相同的情况下尽可能保留更多电量,我们在入队时将剩余电量取负值,使得优先队列在比较时优先选择剩余电量更多的状态。
当取出 \((d, p, u)\) 时:
- 若 \(u = \textit{target}\),直接返回 \([d, p]\);
- 若 \(d > \textit{dist}[u][p]\) 或 \(p < \textit{cost}[u]\),跳过该状态;
- 否则,从节点 \(u\) 转发信号,剩余电量减少 \(\textit{cost}[u]\),然后遍历所有出边 \((v, t)\),尝试更新 \(\textit{dist}[v][p - \textit{cost}[u]] = \min(\textit{dist}[v][p - \textit{cost}[u]], d + t)\)。
若优先队列为空仍未到达目标节点,返回 \([-1, -1]\)。
时间复杂度 \(O((n + m) \textit{power} \log (n \textit{power}))\),空间复杂度 \(O(n \textit{power})\)。其中 \(n\) 和 \(m\) 分别是节点数和边数, \(\textit{power}\) 是初始电量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | class Solution:
def minTimeMaxPower(
self,
n: int,
edges: list[list[int]],
power: int,
cost: list[int],
source: int,
target: int,
) -> list[int]:
g = [[] for _ in range(n)]
for u, v, t in edges:
g[u].append((v, t))
dist = [[inf] * (power + 1) for _ in range(n)]
dist[source][power] = 0
pq = [(0, -power, source)]
while pq:
d, p, u = heappop(pq)
p = -p
if u == target:
return [d, p]
if d > dist[u][p] or p < cost[u]:
continue
p -= cost[u]
for v, t in g[u]:
nd = d + t
if nd < dist[v][p]:
dist[v][p] = nd
heappush(pq, (nd, -p, v))
return [-1, -1]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50 | class Solution {
public long[] minTimeMaxPower(
int n, int[][] edges, int power, int[] cost, int source, int target) {
long inf = Long.MAX_VALUE / 4;
List<int[]>[] g = new ArrayList[n];
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
for (int[] e : edges) {
g[e[0]].add(new int[] {e[1], e[2]});
}
long[][] dist = new long[n][power + 1];
for (int i = 0; i < n; i++) Arrays.fill(dist[i], inf);
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> {
if (a[0] != b[0]) return Long.compare(a[0], b[0]);
return Long.compare(a[1], b[1]);
});
dist[source][power] = 0;
pq.offer(new long[] {0, -power, source});
while (!pq.isEmpty()) {
long[] cur = pq.poll();
long d = cur[0];
int p = (int) -cur[1];
int u = (int) cur[2];
if (u == target) return new long[] {d, p};
if (d > dist[u][p] || p < cost[u]) continue;
p -= cost[u];
for (int[] e : g[u]) {
int v = e[0];
int t = e[1];
long nd = d + t;
if (nd < dist[v][p]) {
dist[v][p] = nd;
pq.offer(new long[] {nd, -p, v});
}
}
}
return new long[] {-1, -1};
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49 | class Solution {
public:
vector<long long> minTimeMaxPower(
int n,
vector<vector<int>>& edges,
int power,
vector<int>& cost,
int source,
int target) {
using ll = long long;
const ll inf = LLONG_MAX / 4;
vector<vector<pair<int, int>>> g(n);
for (auto& e : edges) {
g[e[0]].push_back({e[1], e[2]});
}
vector<vector<ll>> dist(n, vector<ll>(power + 1, inf));
using T = tuple<ll, int, int>;
priority_queue<T, vector<T>, greater<T>> pq;
dist[source][power] = 0;
pq.push({0, -power, source});
while (!pq.empty()) {
auto [d, negp, u] = pq.top();
pq.pop();
int p = -negp;
if (u == target) return {d, p};
if (d > dist[u][p] || p < cost[u]) continue;
p -= cost[u];
for (auto& [v, t] : g[u]) {
ll nd = d + t;
if (nd < dist[v][p]) {
dist[v][p] = nd;
pq.push({nd, -p, v});
}
}
}
return {-1, -1};
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83 | type State struct {
d int64
p int
u int
}
type PQ []State
func (h PQ) Len() int { return len(h) }
func (h PQ) Less(i, j int) bool {
if h[i].d != h[j].d {
return h[i].d < h[j].d
}
return h[i].p < h[j].p
}
func (h PQ) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *PQ) Push(x interface{}) { *h = append(*h, x.(State)) }
func (h *PQ) Pop() interface{} {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
func minTimeMaxPower(
n int,
edges [][]int,
power int,
cost []int,
source int,
target int,
) []int64 {
inf := int64(1 << 62)
g := make([][][]int, n)
for _, e := range edges {
g[e[0]] = append(g[e[0]], []int{e[1], e[2]})
}
dist := make([][]int64, n)
for i := range dist {
dist[i] = make([]int64, power+1)
for j := range dist[i] {
dist[i][j] = inf
}
}
pq := &PQ{}
heap.Push(pq, State{0, -power, source})
dist[source][power] = 0
for pq.Len() > 0 {
cur := heap.Pop(pq).(State)
d := cur.d
p := -cur.p
u := cur.u
if u == target {
return []int64{d, int64(p)}
}
if d > dist[u][p] || p < cost[u] {
continue
}
p -= cost[u]
for _, e := range g[u] {
v, t := e[0], e[1]
nd := d + int64(t)
if nd < dist[v][p] {
dist[v][p] = nd
heap.Push(pq, State{nd, -p, v})
}
}
}
return []int64{-1, -1}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47 | function minTimeMaxPower(
n: number,
edges: number[][],
power: number,
cost: number[],
source: number,
target: number,
): number[] {
const inf = 1e18;
const g: [number, number][][] = Array.from({ length: n }, () => []);
for (const [u, v, t] of edges) {
g[u].push([v, t]);
}
const dist: number[][] = Array.from({ length: n }, () => Array(power + 1).fill(inf));
const pq = new PriorityQueue<number[]>((a, b) => {
if (a[0] !== b[0]) return a[0] - b[0];
return a[1] - b[1];
});
dist[source][power] = 0;
pq.enqueue([0, -power, source]);
while (!pq.isEmpty()) {
const [d, negp, u] = pq.dequeue();
let p = -negp;
if (u === target) return [d, p];
if (d > dist[u][p] || p < cost[u]) continue;
p -= cost[u];
for (const [v, t] of g[u]) {
const nd = d + t;
if (nd < dist[v][p]) {
dist[v][p] = nd;
pq.enqueue([nd, -p, v]);
}
}
}
return [-1, -1];
}
|