题目描述
给定一个正整数 n 和一个二维整数数组 edges，其中 edges[i] = [ui, vi, wi]。
有一个 带权连通 简单无向图，包含 n 个节点，下标从 0 到 n - 1。每条边 [ui, vi, wi] 表示在节点 ui 和节点 vi 之间有一条 正 权边 wi。
路径的 开销 是路径中边的权重之 和，排除 权重 最大 的那条边。如果路径中有多个权重最大的边，只 排除 第一个 这样的边。
返回一个整数表示从节点 0 到节点 n - 1 的 最小 开销。
示例 1：
输入：n = 5, edges = [[0,1,2],[1,2,7],[2,3,7],[3,4,4]]
输出：13
解释：
从节点 0 到节点 4 只有一条路径： 0 -> 1 -> 2 -> 3 -> 4.
路径上边的权重是 2，7，7 和 4。
排除第一条权重最大的边，即 1 -> 2，路径的开销是 2 + 7 + 4 = 13。
示例 2：
输入：n = 3, edges = [[0,1,1],[1,2,1],[0,2,50000]]
输出：0
解释：
从节点 0 到 2 有两条路径：
路径上边的权重是 1 和 1。
排除第一条权重最大的边，即 0 -> 1，路径的开销是 1。
这条路径上唯一的边权重是1。
排除第一条权重最大的边，即 0 -> 2，路径的开销是 0。
最小的开销是 min(1, 0) = 0。
提示：
2 <= n <= 5 * 104n - 1 <= edges.length <= 109edges[i] = [ui, vi, wi]0 <= ui < vi < n[ui, vi] != [uj, vj]1 <= wi <= 5 * 104- 图是连通的。
解法
方法一
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 | class Solution:
def minCostExcludingMax(self, n: int, edges: List[List[int]]) -> int:
g = [[] for _ in range(n)]
for u, v, w in edges:
g[u].append((v, w))
g[v].append((u, w))
dist = [[inf] * 2 for _ in range(n)]
dist[0][0] = 0
pq = [(0, 0, 0)]
while pq:
cur, u, used = heappop(pq)
if cur > dist[u][used]:
continue
if u == n - 1 and used:
return cur
for v, w in g[u]:
nxt = cur + w
if nxt < dist[v][used]:
dist[v][used] = nxt
heappush(pq, (nxt, v, used))
if used == 0:
nxt = cur
if nxt < dist[v][1]:
dist[v][1] = nxt
heappush(pq, (nxt, v, 1))
return dist[n - 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 | class Solution {
public long minCostExcludingMax(int n, int[][] edges) {
List<int[]>[] g = new ArrayList[n];
Arrays.setAll(g, k -> new ArrayList<>());
for (int[] e : edges) {
int u = e[0], v = e[1], w = e[2];
g[u].add(new int[]{v, w});
g[v].add(new int[]{u, w});
}
long inf = Long.MAX_VALUE / 4;
long[][] dist = new long[n][2];
for (int i = 0; i < n; i++) {
dist[i][0] = inf;
dist[i][1] = inf;
}
dist[0][0] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
pq.add(new long[]{0, 0, 0});
while (!pq.isEmpty()) {
long[] t = pq.poll();
long cur = t[0];
int u = (int) t[1];
int used = (int) t[2];
if (cur > dist[u][used]) {
continue;
}
if (u == n - 1 && used == 1) {
return cur;
}
for (int[] ed : g[u]) {
int v = ed[0], w = ed[1];
long nxt = cur + w;
if (nxt < dist[v][used]) {
dist[v][used] = nxt;
pq.add(new long[]{nxt, v, used});
}
if (used == 0) {
nxt = cur;
if (nxt < dist[v][1]) {
dist[v][1] = nxt;
pq.add(new long[]{nxt, v, 1});
}
}
}
}
return dist[n - 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 | class Solution {
public:
long long minCostExcludingMax(int n, vector<vector<int>>& edges) {
vector<vector<pair<int, int>>> g(n);
for (auto& e : edges) {
int u = e[0], v = e[1], w = e[2];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
long long inf = LLONG_MAX / 4;
vector<array<long long, 2>> dist(n, {inf, inf});
dist[0][0] = 0;
priority_queue<array<long long, 3>, vector<array<long long, 3>>, greater<array<long long, 3>>> pq;
pq.push({0, 0, 0});
while (!pq.empty()) {
auto t = pq.top();
pq.pop();
long long cur = t[0];
int u = t[1];
int used = t[2];
if (cur > dist[u][used]) {
continue;
}
if (u == n - 1 && used == 1) {
return cur;
}
for (auto [v, w] : g[u]) {
long long nxt = cur + w;
if (nxt < dist[v][used]) {
dist[v][used] = nxt;
pq.push({nxt, v, used});
}
if (used == 0) {
nxt = cur;
if (nxt < dist[v][1]) {
dist[v][1] = nxt;
pq.push({nxt, v, 1});
}
}
}
}
return dist[n - 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 | func minCostExcludingMax(n int, edges [][]int) int64 {
g := make([][]edge, n)
for _, e := range edges {
u, v, w := e[0], e[1], e[2]
g[u] = append(g[u], edge{v, w})
g[v] = append(g[v], edge{u, w})
}
inf := int64(math.MaxInt64 / 4)
dist := make([][2]int64, n)
for i := 0; i < n; i++ {
dist[i][0] = inf
dist[i][1] = inf
}
dist[0][0] = 0
pq := hp{{0, 0, 0}}
for len(pq) > 0 {
t := heap.Pop(&pq).(state)
cur, u, used := t.cur, t.u, t.used
if cur > dist[u][used] {
continue
}
if u == n-1 && used == 1 {
return cur
}
for _, ed := range g[u] {
v, w := ed.to, int64(ed.w)
nxt := cur + w
if nxt < dist[v][used] {
dist[v][used] = nxt
heap.Push(&pq, state{nxt, v, used})
}
if used == 0 {
nxt = cur
if nxt < dist[v][1] {
dist[v][1] = nxt
heap.Push(&pq, state{nxt, v, 1})
}
}
}
}
return dist[n-1][1]
}
type edge struct {
to int
w int
}
type state struct {
cur int64
u int
used int
}
type hp []state
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].cur < h[j].cur }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(x any) { *h = append(*h, x.(state)) }
func (h *hp) Pop() (x any) { a := *h; x = a[len(a)-1]; *h = a[:len(a)-1]; return }
|
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 | function minCostExcludingMax(n: number, edges: number[][]): number {
const g: [number, number][][] = Array.from({ length: n }, () => []);
for (const [u, v, w] of edges) {
g[u].push([v, w]);
g[v].push([u, w]);
}
const INF = Infinity;
const dist: number[][] = Array.from({ length: n }, () => [INF, INF]);
dist[0][0] = 0;
const pq = new PriorityQueue<[number, number, number]>((a, b) =>
a[0] === b[0] ? a[1] - b[1] : a[0] - b[0],
);
pq.enqueue([0, 0, 0]);
while (pq.size() > 0) {
const [cur, u, used] = pq.dequeue()!;
if (cur > dist[u][used]) {
continue;
}
if (u === n - 1 && used === 1) {
return cur;
}
for (const [v, w] of g[u]) {
const nxt1 = cur + w;
if (nxt1 < dist[v][used]) {
dist[v][used] = nxt1;
pq.enqueue([nxt1, v, used]);
}
if (used === 0) {
const nxt2 = cur;
if (nxt2 < dist[v][1]) {
dist[v][1] = nxt2;
pq.enqueue([nxt2, v, 1]);
}
}
}
}
return dist[n - 1][1];
}
|