列表

详情

1928. 规定时间内到达终点的最小花费

一个国家有 n 个城市，城市编号为 0 到 n - 1 ，题目保证 所有城市 都由双向道路 连接在一起 。道路由二维整数数组 edges 表示，其中 edges[i] = [xi, yi, timei] 表示城市 xi 和 yi 之间有一条双向道路，耗费时间为 timei 分钟。两个城市之间可能会有多条耗费时间不同的道路，但是不会有道路两头连接着同一座城市。

每次经过一个城市时，你需要付通行费。通行费用一个长度为 n 且下标从 0 开始的整数数组 passingFees 表示，其中 passingFees[j] 是你经过城市 j 需要支付的费用。

一开始，你在城市 0 ，你想要在 maxTime 分钟以内 （包含 maxTime 分钟）到达城市 n - 1 。旅行的 费用 为你经过的所有城市 通行费之和 （包括 起点和终点城市的通行费）。

给你 maxTime，edges 和 passingFees ，请你返回完成旅行的 最小费用 ，如果无法在 maxTime 分钟以内完成旅行，请你返回 -1 。

 

示例 1：

输入：maxTime = 30, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
输出：11
解释：最优路径为 0 -> 1 -> 2 -> 5 ，总共需要耗费 30 分钟，需要支付 11 的通行费。

示例 2：

输入：maxTime = 29, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
输出：48
解释：最优路径为 0 -> 3 -> 4 -> 5 ，总共需要耗费 26 分钟，需要支付 48 的通行费。
你不能选择路径 0 -> 1 -> 2 -> 5 ，因为这条路径耗费的时间太长。

示例 3：

输入：maxTime = 25, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
输出：-1
解释：无法在 25 分钟以内从城市 0 到达城市 5 。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) { } };

rust 解法, 执行用时: 79 ms, 内存消耗: 5.9 MB, 提交时间: 2024-10-03 08:54:46 

use std::cmp::min;

impl Solution {
    pub fn min_cost(max_time: i32, edges: Vec<Vec<i32>>, passing_fees: Vec<i32>) -> i32 {
        let n = passing_fees.len();
        let mut f = vec![vec![i32::MAX; n]; (max_time + 1) as usize];
        f[0][0] = passing_fees[0];

        for t in 1..=max_time {
            for edge in &edges {
                let (i, j, cost) = (edge[0] as usize, edge[1] as usize, edge[2]);
                if cost <= t {
                    if f[(t - cost) as usize][j] != i32::MAX {
                        f[t as usize][i] = min(f[t as usize][i], f[(t - cost) as usize][j] + passing_fees[i]);
                    }
                    if f[(t - cost) as usize][i] != i32::MAX {
                        f[t as usize][j] = min(f[t as usize][j], f[(t - cost) as usize][i] + passing_fees[j]);
                    }
                }
            }
        }

        let mut ans = i32::MAX;
        for t in 1..=max_time {
            ans = min(ans, f[t as usize][n - 1]);
        }
        if ans == i32::MAX {
            -1
        } else {
            ans
        }
    }
}

javascript 解法, 执行用时: 497 ms, 内存消耗: 76.5 MB, 提交时间: 2024-10-03 08:54:02 

/**
 * @param {number} maxTime
 * @param {number[][]} edges
 * @param {number[]} passingFees
 * @return {number}
 */
var minCost = function(maxTime, edges, passingFees) {
    const n = passingFees.length;
    const f = Array.from({ length: maxTime + 1 }, () => Array(n).fill(Infinity));
    f[0][0] = passingFees[0];
    for (let t = 1; t <= maxTime; t++) {
        for (const [i, j, cost] of edges) {
            if (cost <= t) {
                if (f[t - cost][j] !== Infinity) {
                    f[t][i] = Math.min(f[t][i], f[t - cost][j] + passingFees[i]);
                }
                if (f[t - cost][i] !== Infinity) {
                    f[t][j] = Math.min(f[t][j], f[t - cost][i] + passingFees[j]);
                }
            }
        }
    }

    let ans = Infinity;
    for (let t = 1; t <= maxTime; t++) {
        ans = Math.min(ans, f[t][n - 1]);
    }
    return ans === Infinity ? -1 : ans;
};

golang 解法, 执行用时: 40 ms, 内存消耗: 7.1 MB, 提交时间: 2023-10-27 22:17:07 

var minFee = 10000000
var vis []bool
var lastVisTime []int
var lastVisFee []int
type pairs struct {
	city, time, fee int
}

func minCost(maxTime int, edges [][]int, passingFees []int) int {
	minFee = 10000000
	prs := make([][]pairs, len(passingFees)) // 邻接表
	vis = make([]bool, len(passingFees))
	vis[0] = true
	lastVisTime = make([]int, len(passingFees))
	lastVisFee = make([]int, len(passingFees))
	for i := range lastVisFee {
		lastVisFee[i] = math.MaxInt32
		lastVisTime[i] = math.MaxInt32
	}
	for _, e := range edges {
		prs[e[0]] = append(prs[e[0]], pairs{
			city: e[1],
			time: e[2],
			fee:  passingFees[e[1]],
		})
		prs[e[1]] = append(prs[e[1]], pairs{
			city: e[0],
			time: e[2],
			fee:  passingFees[e[0]],
		})
	}
	dfs(maxTime, prs, 0, passingFees[0], 0)
	if minFee == 10000000 {
		return -1
	}
	return minFee
}

func dfs(maxTime int, prs [][]pairs, curCity int, curFee, curTime int)  {
	if curTime > maxTime || curFee >= minFee{
		return
	}
	if curFee > lastVisFee[curCity] && curTime > lastVisTime[curCity] {
		return
	}
	lastVisFee[curCity] = min(lastVisFee[curCity], curFee)
	lastVisTime[curCity] = min(lastVisTime[curCity], curTime)
	if curCity == len(prs) - 1 {
		minFee = curFee
		return
	}
	for _, nx := range prs[curCity] {
		if !vis[nx.city] {
			vis[nx.city] = true
			dfs(maxTime, prs, nx.city, curFee + nx.fee, curTime + nx.time)
			vis[nx.city] = false
		}
	}
}

func min(i,j int) int {
	if i < j {
		return i
	}
	return j
}

java 解法, 执行用时: 90 ms, 内存消耗: 54 MB, 提交时间: 2023-10-27 22:16:27 

import java.util.Arrays;

class Solution {
    public int minCost(int maxTime, int[][] edges, int[] passingFees) {
        int n=passingFees.length;
        int INF=Integer.MAX_VALUE/2;
        int[][]dp=new int[maxTime+1][n];
        for(int i=0;i<dp.length;i++) Arrays.fill(dp[i],INF);
        //初始化  对动态规划的状态定义dp[i][j] i是花费的时间 j是所到达的城市
         dp[0][0]=passingFees[0];
        //
        int res=INF;
        for(int t=1;t<=maxTime;t++){
            for(int i=0;i<edges.length;i++){
                int[]v=edges[i];
                int x=v[0];//x->y
                int y=v[1];//y->X
                int cost=v[2];
                if(cost<=t){
                    dp[t][y]=Math.min(dp[t][y],dp[t-cost][x]+passingFees[y]);
                    dp[t][x]=Math.min(dp[t][x],dp[t-cost][y]+passingFees[x]);
                }
            }
            res=Math.min(res,dp[t][n-1]);
        }
      return  res==INF?-1:res;
    }
}

python3 解法, 执行用时: 7276 ms, 内存消耗: 39.1 MB, 提交时间: 2023-10-27 22:15:59 

class Solution:
    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
        n = len(passingFees)
        # f[t][i] 表示使用恰好 t 分钟到达城市 i 需要的最少通行费总和。
        f = [[float("inf")] * n for _ in range(maxTime + 1)]
        f[0][0] = passingFees[0]
        for t in range(1, maxTime + 1):
            for i, j, cost in edges:
                if cost <= t:
                    f[t][i] = min(f[t][i], f[t - cost][j] + passingFees[i])
                    f[t][j] = min(f[t][j], f[t - cost][i] + passingFees[j])

        ans = min(f[t][n - 1] for t in range(1, maxTime + 1))
        return -1 if ans == float("inf") else ans

cpp 解法, 执行用时: 740 ms, 内存消耗: 91.3 MB, 提交时间: 2023-10-27 22:15:25 

class Solution {
private:
    // 极大值
    static constexpr int INFTY = INT_MAX / 2;

public:
    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
        int n = passingFees.size();
        vector<vector<int>> f(maxTime + 1, vector<int>(n, INFTY));
        f[0][0] = passingFees[0];
        for (int t = 1; t <= maxTime; ++t) {
            for (const auto& edge: edges) {
                int i = edge[0], j = edge[1], cost = edge[2];
                if (cost <= t) {
                    f[t][i] = min(f[t][i], f[t - cost][j] + passingFees[i]);
                    f[t][j] = min(f[t][j], f[t - cost][i] + passingFees[j]);
                }
            }
        }

        int ans = INFTY;
        for (int t = 1; t <= maxTime; ++t) {
            ans = min(ans, f[t][n - 1]);
        }
        return ans == INFTY ? -1 : ans;
    }
};

上一题

© 2024 leetcode.cn