最大化一张图中的路径价值

2065. 最大化一张图中的路径价值

给你一张无向图，图中有 n 个节点，节点编号从 0 到 n - 1 （都包括）。同时给你一个下标从 0 开始的整数数组 values ，其中 values[i] 是第 i 个节点的价值。同时给你一个下标从 0 开始的二维整数数组 edges ，其中 edges[j] = [u_j, v_j, time_j] 表示节点 u_j 和 v_j 之间有一条需要 time_j 秒才能通过的无向边。最后，给你一个整数 maxTime 。

合法路径 指的是图中任意一条从节点 0 开始，最终回到节点 0 ，且花费的总时间 不超过 maxTime 秒的一条路径。你可以访问一个节点任意次。一条合法路径的价值定义为路径中 不同节点 的价值之和（每个节点的价值至多算入价值总和中一次）。

请你返回一条合法路径的最大价值。

注意：每个节点至多有四条边与之相连。

示例 1：

输入：values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49
输出：75
解释：
一条可能的路径为：0 -> 1 -> 0 -> 3 -> 0 。总花费时间为 10 + 10 + 10 + 10 = 40 <= 49 。
访问过的节点为 0 ，1 和 3 ，最大路径价值为 0 + 32 + 43 = 75 。

示例 2：

输入：values = [5,10,15,20], edges = [[0,1,10],[1,2,10],[0,3,10]], maxTime = 30
输出：25
解释：
一条可能的路径为：0 -> 3 -> 0 。总花费时间为 10 + 10 = 20 <= 30 。
访问过的节点为 0 和 3 ，最大路径价值为 5 + 20 = 25 。

示例 3：

输入：values = [1,2,3,4], edges = [[0,1,10],[1,2,11],[2,3,12],[1,3,13]], maxTime = 50
输出：7
解释：
一条可能的路径为：0 -> 1 -> 3 -> 1 -> 0 。总花费时间为 10 + 13 + 13 + 10 = 46 <= 50 。
访问过的节点为 0 ，1 和 3 ，最大路径价值为 1 + 2 + 4 = 7 。

示例 4：

输入：values = [0,1,2], edges = [[1,2,10]], maxTime = 10
输出：0
解释：
唯一一条路径为 0 。总花费时间为 0 。
唯一访问过的节点为 0 ，最大路径价值为 0 。

提示：

n == values.length
1 <= n <= 1000
0 <= values[i] <= 10⁸
0 <= edges.length <= 2000
edges[j].length == 3
0 <= u_j< v_j <= n - 1
10 <= time_j, maxTime <= 100
[u_j, v_j] 所有节点对 互不相同 。
每个节点 至多有四条 边。
图可能不连通。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) { } };

rust 解法, 执行用时: 6 ms, 内存消耗: 2.3 MB, 提交时间: 2024-07-01 09:07:56

use std::collections::BinaryHeap;

impl Solution {
    pub fn maximal_path_quality(values: Vec<i32>, edges: Vec<Vec<i32>>, max_time: i32) -> i32 {
        let n = values.len();
        let mut g = vec![vec![]; n];
        for e in edges {
            let x = e[0] as usize;
            let y = e[1] as usize;
            let t = e[2];
            g[x].push((y, t));
            g[y].push((x, t));
        }

        // Dijkstra 算法
        let mut dis = vec![i32::MAX; n];
        dis[0] = 0;
        let mut h = BinaryHeap::new();
        h.push((0, 0));
        while let Some((dx, x)) = h.pop() {
            if -dx > dis[x] { // x 之前出堆过
                continue;
            }
            for &(y, t) in &g[x] {
                let new_dis = -dx + t;
                if new_dis < dis[y] {
                    dis[y] = new_dis; // 更新 x 的邻居的最短路
                    h.push((-new_dis, y));
                }
            }
        }

        fn dfs(x: usize, sum_time: i32, sum_value: i32, vis: &mut Vec<bool>, g: &Vec<Vec<(usize, i32)>>, values: &Vec<i32>, max_time: i32, dis: &Vec<i32>) -> i32 {
            let mut ans = if x == 0 { sum_value } else { 0 };
            for &(y, t) in &g[x] {
                // 相比方法一，这里多了 dis[y]
                if sum_time + t + dis[y] > max_time {
                    continue;
                }
                if vis[y] {
                    ans = ans.max(dfs(y, sum_time + t, sum_value, vis, g, values, max_time, dis));
                } else {
                    vis[y] = true;
                    // 每个节点的价值至多算入价值总和中一次
                    ans = ans.max(dfs(y, sum_time + t, sum_value + values[y], vis, g, values, max_time, dis));
                    vis[y] = false; // 恢复现场
                }
            }
            ans
        }

        let mut vis = vec![false; n];
        vis[0] = true;
        dfs(0, 0, values[0], &mut vis, &g, &values, max_time, &dis)
    }
}

javascript 解法, 执行用时: 116 ms, 内存消耗: 58.9 MB, 提交时间: 2024-07-01 09:07:35

/**
 * @param {number[]} values
 * @param {number[][]} edges
 * @param {number} maxTime
 * @return {number}
 */
var maximalPathQuality = function(values, edges, maxTime) {
    const n = values.length;
    const g = Array.from({ length: n }, () => []);
    for (const [x, y, t] of edges) {
        g[x].push([y, t]);
        g[y].push([x, t]);
    }

    // Dijkstra 算法
    const dis = Array(n).fill(Infinity);
    dis[0] = 0;
    const pq =  new MinPriorityQueue({priority: (p) => p[0]});
    pq.enqueue([0, 0]);
    while (!pq.isEmpty()) {
        const [dx, x] = pq.dequeue().element;
        if (dx > dis[x]) { // x 之前出堆过
            continue;
        }
        for (const [y, t] of g[x]) {
            const new_dis = dx + t;
            if (new_dis < dis[y]) {
                dis[y] = new_dis; // 更新 x 的邻居的最短路
                pq.enqueue([new_dis, y]);
            }
        }
    }

    let ans = 0;
    const vis = Array(n).fill(false);
    vis[0] = true;
    function dfs(x, sumTime, sumValue) {
        if (x === 0) {
            ans = Math.max(ans, sumValue);
            // 注意这里没有 return，还可以继续走
        }
        for (const [y, t] of g[x]) {
            // 相比方法一，这里多了 dis[y]
            if (sumTime + t + dis[y] > maxTime) {
                continue;
            }
            if (vis[y]) {
                dfs(y, sumTime + t, sumValue);
            } else {
                vis[y] = true;
                // 每个节点的价值至多算入价值总和中一次
                dfs(y, sumTime + t, sumValue + values[y]);
                vis[y] = false; // 恢复现场
            }
        }
    }
    dfs(0, 0, values[0]);
    return ans;
};

python3 解法, 执行用时: 1028 ms, 内存消耗: 18 MB, 提交时间: 2023-10-25 23:08:36

class Solution:
    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:
        g = defaultdict(list)
        for x, y, z in edges:
            g[x].append((y, z))
            g[y].append((x, z))
        
        visited = {0}
        ans = 0
        
        def dfs(u: int, time: int, value: int) -> None:
            if u == 0:
                nonlocal ans
                ans = max(ans, value)
            for v, dist in g[u]:
                if time + dist <= maxTime:
                    if v not in visited:
                        visited.add(v)
                        dfs(v, time + dist, value + values[v])
                        visited.discard(v)
                    else:
                        dfs(v, time + dist, value)
        
        dfs(0, 0, values[0])
        return ans

cpp 解法, 执行用时: 168 ms, 内存消耗: 20.8 MB, 提交时间: 2023-10-25 23:08:17

class Solution {
public:
    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
        int n = values.size();
        vector<vector<pair<int, int>>> g(n);
        for (const auto& edge: edges) {
            g[edge[0]].emplace_back(edge[1], edge[2]);
            g[edge[1]].emplace_back(edge[0], edge[2]);
        }
        
        vector<int> visited(n);
        visited[0] = true;
        int ans = 0;
        
        function<void(int, int, int)> dfs = [&](int u, int time, int value) {
            if (u == 0) {
                ans = max(ans, value);
            }
            for (const auto& [v, dist]: g[u]) {
                if (time + dist <= maxTime) {
                    if (!visited[v]) {
                        visited[v] = true;
                        dfs(v, time + dist, value + values[v]);
                        visited[v] = false;
                    }
                    else {
                        dfs(v, time + dist, value);
                    }
                }
            }
        };
        
        dfs(0, 0, values[0]);
        return ans;
    }
};

golang 解法, 执行用时: 40 ms, 内存消耗: 6.5 MB, 提交时间: 2023-10-25 23:07:54

func maximalPathQuality(values []int, edges [][]int, maxTime int) (ans int) {
	n := len(values)
	g := make([][]edge, n)
	for _, e := range edges {
		v, w, t := e[0], e[1], e[2]
		g[v] = append(g[v], edge{w, t}) // 建图
		g[w] = append(g[w], edge{v, t})
	}

	dis := dijkstra(g, 0) // 预处理从起点 0 到每个点的最短路

	vis := make([]bool, n)
	sum := 0
	var dfs func(int, int)
	dfs = func(v, time int) {
		if !vis[v] { // 没有访问时，更新价值之和
			vis[v] = true
			sum += values[v]
			if sum > ans {
				ans = sum // 更新答案
			}
			defer func() {
				sum -= values[v] // 恢复现场
				vis[v] = false
			}()
		}
		for _, e := range g[v] {
			if time+e.t+dis[e.to] <= maxTime { // 剪枝：下个节点在走最短路的情况下可以在 maxTime 时间内返回起点 0
				dfs(e.to, time+e.t)
			}
		}
	}
	dfs(0, 0)
	return
}

// 下面是求最短路的模板
type edge struct{ to, t int }
type pair struct{ v, dis int }
type hp []pair

func (h hp) Len() int              { return len(h) }
func (h hp) Less(i, j int) bool    { return h[i].dis < h[j].dis }
func (h hp) Swap(i, j int)         { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{})   { *h = append(*h, v.(pair)) }
func (h *hp) Pop() (v interface{}) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }
func (h *hp) push(v pair)          { heap.Push(h, v) }
func (h *hp) pop() pair            { return heap.Pop(h).(pair) }

func dijkstra(g [][]edge, start int) []int {
	dis := make([]int, len(g))
	for i := range dis {
		dis[i] = 1e9
	}
	dis[start] = 0
	h := hp{{start, 0}}
	for len(h) > 0 {
		vd := h.pop()
		v := vd.v
		if dis[v] < vd.dis {
			continue
		}
		for _, e := range g[v] {
			w, wt := e.to, e.t
			if newD := dis[v] + wt; newD < dis[w] {
				dis[w] = newD
				h.push(pair{w, dis[w]})
			}
		}
	}
	return dis
}

java 解法, 执行用时: 191 ms, 内存消耗: 43.3 MB, 提交时间: 2023-10-25 23:07:37

class Solution {
    Map<Integer, List<int[]> > graphM=new HashMap<>();
    int ans=0;
    //List<Integer> path=new ArrayList<>();//用作debug
    int[] values; int[][] edges; int maxTime;
    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
        this.values=values; this.edges=edges; this.maxTime=maxTime;
        int lenN=values.length;
        //初始化,存图
        for(int[] edge:edges){
            int stN=edge[0],endN=edge[1],val=edge[2];
            graphM.putIfAbsent(stN,new ArrayList<>());
            graphM.putIfAbsent(endN,new ArrayList<>());
            graphM.get(stN).add(new int[]{endN,val});
            graphM.get(endN).add(new int[]{stN,val});
        }
        dfs(0,0,0);
        return ans;
    }
    public void dfs(int startN, int curTime, int curValue){
        //path.add(startN);
        int temp=values[startN];
        curValue += temp;
        //访问过节点置0，防止重复累加
        values[startN]=0;
        if(startN==0){
            ans=Math.max(ans,curValue);
        }
        if(null==graphM.get(startN)){
            return;
        }else{
            for(int[] nextN:graphM.get(startN)){
                if(curTime+nextN[1]>maxTime){continue;}
                dfs(nextN[0],curTime+nextN[1],curValue);
            }
        }
        //还原现场
        //path.remove(path.size()-1);
        values[startN]=temp;
        return;
    }
}

cpp 解法, 执行用时: 196 ms, 内存消耗: 22.8 MB, 提交时间: 2023-10-25 23:07:10

class Solution {
public:
    unordered_map<int, vector<pair<int, int>>> graph;
    int ans = 0;
    
    void dfs(vector<int>& values, int start, int time, int value, int maxTime, vector<int>& path) {
        path.push_back(start);
        int lastV = values[start];
        value += values[start];
        values[start] = 0;
        if (start == 0) {
            // for (auto node: path) {
            //     cout << node << " -> ";
            // }
            // cout << endl;
            ans = max(ans, value);
            // cout << ans << endl;
        }
        for (auto n: graph[start]) {
            if (n.second + time > maxTime) {
                continue;
            }
            dfs(values, n.first, time + n.second, value, maxTime, path);
        }
        path.pop_back();
        values[start] = lastV;
        return;
    }
    
    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
        for (auto e: edges) {
            graph[e[0]].push_back(make_pair(e[1], e[2]));
            graph[e[1]].push_back(make_pair(e[0], e[2]));
        }
        vector<int> path;
        
        dfs(values, 0, 0, 0, maxTime, path);
        
        return ans;
    }
};

上一题

下一题

详情