【动态规划】【图论】【C++算法】1928规定时间内到达终点的最小花费

简介: 【动态规划】【图论】【C++算法】1928规定时间内到达终点的最小花费

作者推荐

【动态规划】【状态压缩】【2次选择】【广度搜索】1494. 并行课程 II

本文涉及知识点

动态规划汇总

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

一个国家有 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 。

提示:

1 <= maxTime <= 1000

n == passingFees.length

2 <= n <= 1000

n - 1 <= edges.length <= 1000

0 <= xi, yi <= n - 1

1 <= timei <= 1000

1 <= passingFees[j] <= 1000

图中两个节点之间可能有多条路径。

图中不含有自环。

动态规划

路径中不会有重复节点,否则去掉环,用时更少,过路费更少或不变。

动态规划的状态表示

dp[i][j] 表示 消耗j单位时间到达i城市的最小过路非。所有相同时间的状态全部更新完时间复杂度是O(n),时间数是maxTime。故总时间复杂度是:O(n*maxTime)。

动态规划的转移方程

前置状态转移后置状态。

dp[i][j]更 新 k 和 i 连接 \Large更新 _{k和i连接}ki连接 dp[k][j+ik需要的时间] =min(,dp[i][j]+pass[k]

动态规划的初始值

dp[0][0]=第一个城市的过路费 其它状态全部为2e6。

动态规划的填表顺序

时间从0到大。

动态规划的返回值

dp.back()的最小值。

代码

class Solution {
public:
  int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
    m_c = passingFees.size();
    CNeiBo3 neiBo(m_c, edges,false);
    vector<vector<int>> dp(m_c, vector<int>(maxTime + 1, m_iNotMay));
    dp[0][0] = passingFees[0];
    for (int time = 0; time < maxTime; time++)
    {
      for (int pos = 0; pos < m_c; pos++)
      {
        for (const auto& [next,useTime] : neiBo.m_vNeiB[pos])
        {
          const int newTime = time + useTime;
          if (newTime <= maxTime)
          {
            const int newFees = dp[pos][time] + passingFees[next];
            if (newFees < dp[next][newTime])
            {
              dp[next][newTime] = newFees;
            }
          }
        }
      }
    }
    const int iMin = *std::min_element(dp.back().begin(), dp.back().end());
    return (iMin >= m_iNotMay) ? -1 : iMin;
  }
  int m_c;
  const int m_iNotMay = 2000'000;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{ 
  int maxTime;
  vector<vector<int>> edges;
  vector<int> passingFees;
  {
    Solution sln;
    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 };
    auto res = sln.minCost(maxTime, edges, passingFees);
    Assert(res,11);
  }
  {
    Solution sln;
    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 };
    auto res = sln.minCost(maxTime, edges, passingFees);
    Assert(res, 48);
  }
  {
    Solution sln;
    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 };
    auto res = sln.minCost(maxTime, edges, passingFees);
    Assert(res, -1);
  }
}

2023年2月版

class Solution {

public:

int minCost(int maxTime, vector<vector>& edges, vector& passingFees) {

m_c = passingFees.size();

m_mDirectTime.resize(m_c);

for (const auto& v : edges)

{

if (v[2] > maxTime)

{

continue;

}

if (0 != m_mDirectTime[v[0]][v[1]] )

{

if (m_mDirectTime[v[0]][v[1]] < v[2])

{

continue;

}

}

m_mDirectTime[v[0]][v[1]] = v[2];

m_mDirectTime[v[1]][v[0]] = v[2];

}

dp.assign(maxTime+1, vector(m_c, m_iNotMay));

dp[0][0] = passingFees[0];

for (int iTime = 0; iTime <= maxTime; iTime++)

{

for (int iPos = 0; iPos < m_c; iPos++)

{

const int& iCurFees = dp[iTime][iPos];

if (m_iNotMay == iCurFees)

{

continue;

}

for (auto it : m_mDirectTime[iPos] )

{

const int iNewTime = iTime + it.second;

if (iNewTime > maxTime)

{

continue;

}

int& iNewFees = dp[iNewTime][it.first];

iNewFees = min(iNewFees, iCurFees + passingFees[it.first]);

}

}

}

int iMinFeel = INT_MAX;

for (auto& v : dp)

{

iMinFeel = min(iMinFeel, v[m_c - 1]);

}

return ( m_iNotMay == iMinFeel) ? -1 : iMinFeel;

}

int m_c;

vector<vector> dp;

vector<std::unordered_map<int, int>> m_mDirectTime;

const int m_iNotMay = 1000 * 1000 * 1000;

};

2023年7月版

class Solution {

public:

int minCost(int maxTime, vector<vector>& edges, vector& passingFees) {

m_c = passingFees.size();

vector<vector> vTimeNodeToMinCost(maxTime + 1, vector(m_c, INT_MAX));

vTimeNodeToMinCost[0][0] = passingFees[0];

for (int time = 1; time <= maxTime; time++)

{

for (const auto& v : edges)

{

Do(v[0], v[1], v[2], time, vTimeNodeToMinCost, passingFees);

Do(v[1], v[0], v[2], time, vTimeNodeToMinCost, passingFees);

}

}

int iMinCost = INT_MAX;

for (const auto& v : vTimeNodeToMinCost)

{

iMinCost = min(iMinCost, v.back());

}

return (INT_MAX == iMinCost) ? -1 : iMinCost;

}

void Do(int pre, int cur, int iUseTime,int time, vector<vector>& vTimeNodeToMinCost, const vector& passingFees)

{

int preTime = time - iUseTime;

if (preTime < 0)

{

return;

}

const int preMinCost = vTimeNodeToMinCost[preTime][pre];

if (INT_MAX == preMinCost)

{

return;

}

vTimeNodeToMinCost[time][cur] = min(vTimeNodeToMinCost[time][cur], preMinCost + passingFees[cur]);

}

int m_c;
vector < vector<pair<int, int>>> m_vNeiB;
int m_iMinCost = INT_MAX;
int m_iMaxTime;

};

2023年9月

class Solution {

public:

int minCost(int maxTime, vector<vector>& edges, vector& passingFees) {

m_iCityNum = passingFees.size();

std::unordered_map<int, int> mNodeNodeToTime[1001];

for (const auto& v : edges)

{

if (!mNodeNodeToTime[v[0]].count(v[1]) || (mNodeNodeToTime[v[0]][v[1]] > v[2]))

{

mNodeNodeToTime[v[0]][v[1]] = v[2];

mNodeNodeToTime[v[1]][v[0]] = v[2];

}

}

for (int i = 0; i < m_iCityNum; i++)

{

m_vNeiBo[i] = vector<pair<int, int>>(mNodeNodeToTime[i].begin(), mNodeNodeToTime[i].end());

}

return Do(maxTime, passingFees);

}

int Do(int maxTime, vector& passingFees)

{

vector vMinFee(m_iCityNum,INT_MAX);

std::priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, std::greater<>> minHeap;

minHeap.emplace(0, 0, passingFees[0]);//总耗时,当前城市,最小消耗

while (minHeap.size())

{

const auto [time, city, fee] = minHeap.top();

minHeap.pop();

if (vMinFee[city] <= fee)

{

continue;

}

else

{

vMinFee[city] = fee;

}

for (const auto& [next, useTime] : m_vNeiBo[city])

{

const int iNewTime = time + useTime;

if (iNewTime > maxTime)

{

continue;

}

const int iNewFee = fee + passingFees[next];

minHeap.emplace(iNewTime, next, iNewFee);

}

}

return ( INT_MAX == vMinFee[m_iCityNum-1] ) ? -1 : vMinFee[m_iCityNum - 1];

}

vector<pair<int, int>> m_vNeiBo[1001];

int m_iCityNum;

};


相关文章
|
21天前
|
机器学习/深度学习 存储 算法
动态规划算法深度解析:0-1背包问题
0-1背包问题是经典的组合优化问题,目标是在给定物品重量和价值及背包容量限制下,选取物品使得总价值最大化且每个物品仅能被选一次。该问题通常采用动态规划方法解决,通过构建二维状态表dp[i][j]记录前i个物品在容量j时的最大价值,利用状态转移方程避免重复计算子问题,从而高效求解最优解。
244 1
|
5月前
|
存储 监控 算法
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下,局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段,已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”,实时捕获每台电脑屏幕上的操作动态。然而,面对海量监控数据,实现高效数据存储与快速检索,已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法,深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”,并通过详尽的代码示例,展现其强大功能与应用价值。
116 2
|
6月前
|
存储 算法 C++
Windows共享文件:探秘C++实现的B树索引算法奇境
在数字化时代,Windows共享文件的高效管理至关重要。B树算法以其自平衡多路搜索特性,在文件索引与存储优化中表现出色。本文探讨B树在Windows共享文件中的应用,通过C++实现具体代码,展示其构建文件索引、优化数据存储的能力,提升文件检索效率。B树通过减少磁盘I/O操作,确保查询高效,为企业和个人提供流畅的文件共享体验。
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
91 0
|
4月前
|
存储 机器学习/深度学习 算法
基于 C++ 的局域网访问控制列表(ACL)实现及局域网限制上网软件算法研究
本文探讨局域网限制上网软件中访问控制列表(ACL)的应用,分析其通过规则匹配管理网络资源访问的核心机制。基于C++实现ACL算法原型,展示其灵活性与安全性。文中强调ACL在企业与教育场景下的重要作用,并提出性能优化及结合机器学习等未来研究方向。
109 4
|
5月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
147 17
|
4月前
|
机器学习/深度学习 存储 算法
基于 C++ 布隆过滤器算法的局域网上网行为控制:URL 访问过滤的高效实现研究
本文探讨了一种基于布隆过滤器的局域网上网行为控制方法,旨在解决传统黑白名单机制在处理海量URL数据时存储与查询效率低的问题。通过C++实现URL访问过滤功能,实验表明该方法可将内存占用降至传统方案的八分之一,查询速度提升约40%,假阳性率可控。研究为优化企业网络管理提供了新思路,并提出结合机器学习、改进哈希函数及分布式协同等未来优化方向。
95 0
|
6月前
|
存储 监控 算法
基于 C++ 哈希表算法的局域网如何监控电脑技术解析
当代数字化办公与生活环境中,局域网的广泛应用极大地提升了信息交互的效率与便捷性。然而,出于网络安全管理、资源合理分配以及合规性要求等多方面的考量,对局域网内计算机进行有效监控成为一项至关重要的任务。实现局域网内计算机监控,涉及多种数据结构与算法的运用。本文聚焦于 C++ 编程语言中的哈希表算法,深入探讨其在局域网计算机监控场景中的应用,并通过详尽的代码示例进行阐释。
122 4
|
7月前
|
存储 算法 安全
企业员工数据泄露防范策略:基于 C++ 语言的布隆过滤器算法剖析[如何防止员工泄密]
企业运营过程中,防范员工泄密是信息安全领域的核心议题。员工泄密可能致使企业核心数据、商业机密等关键资产的流失,进而给企业造成严重损失。为应对这一挑战,借助恰当的数据结构与算法成为强化信息防护的有效路径。本文专注于 C++ 语言中的布隆过滤器算法,深入探究其在防范员工泄密场景中的应用。
119 8
|
8月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。

热门文章

最新文章