【动态规划】【图论】【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连接}更新k和i连接 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;

};