遂宁模板建站公司,如何制作网站页面,网站安全检测方法,图片上加语音 网站开发作者推荐
视频算法专题
LeetCode2045. 到达目的地的第二短时间
城市用一个 双向连通 图表示#xff0c;图中有 n 个节点#xff0c;从 1 到 n 编号#xff08;包含 1 和 n#xff09;。图中的边用一个二维整数数组 edges 表示#xff0c;其中每个 edges[i] [ui, vi] 表…作者推荐
视频算法专题
LeetCode2045. 到达目的地的第二短时间
城市用一个 双向连通 图表示图中有 n 个节点从 1 到 n 编号包含 1 和 n。图中的边用一个二维整数数组 edges 表示其中每个 edges[i] [ui, vi] 表示一条节点 ui 和节点 vi 之间的双向连通边。每组节点对由 最多一条 边连通顶点不存在连接到自身的边。穿过任意一条边的时间是 time 分钟。 每个节点都有一个交通信号灯每 change 分钟改变一次从绿色变成红色再由红色变成绿色循环往复。所有信号灯都 同时 改变。你可以在 任何时候 进入某个节点但是 只能 在节点 信号灯是绿色时 才能离开。如果信号灯是 绿色 你 不能 在节点等待必须离开。 第二小的值 是 严格大于 最小值的所有值中最小的值。 例如[2, 3, 4] 中第二小的值是 3 而 [2, 2, 4] 中第二小的值是 4 。 给你 n、edges、time 和 change 返回从节点 1 到节点 n 需要的 第二短时间 。 注意 你可以 任意次 穿过任意顶点包括 1 和 n 。 你可以假设在 启程时 所有信号灯刚刚变成 绿色 。 示例 1 输入n 5, edges [[1,2],[1,3],[1,4],[3,4],[4,5]], time 3, change 5 输出13
解释 上面的左图展现了给出的城市交通图。 右图中的蓝色路径是最短时间路径。 花费的时间是
从节点 1 开始总花费时间01 - 43 分钟总花费时间34 - 53 分钟总花费时间6 因此需要的最小时间是 6 分钟。 右图中的红色路径是第二短时间路径。从节点 1 开始总花费时间01 - 33 分钟总花费时间33 - 43 分钟总花费时间6在节点 4 等待 4 分钟总花费时间104 - 53 分钟总花费时间13 因此第二短时间是 13 分钟。 示例 2 输入n 2, edges [[1,2]], time 3, change 2 输出11 解释 最短时间路径是 1 - 2 总花费时间 3 分钟 第二短时间路径是 1 - 2 - 1 - 2 总花费时间 11 分钟
提示
2 n 104 n - 1 edges.length min(2 * 104, n * (n - 1) / 2) edges[i].length 2 1 ui, vi n ui ! vi 不含重复边 每个节点都可以从其他节点直接或者间接到达 1 time, change 103
深度优先
经过的边数相同则行驶时间相同等待时间也相同。所以本题等效与求严格经过边数第二少。令经过最少的边数是x则严格第二少的边数只能是x1或x2。因为到达目的地后返回一个节点再到达目的地经过的边数是x2。 本问题等于与 一计算最少经过边数x。 二能否经过x1条边到达目的的。
每个节点除了记录最少边数还要记录另外一个状态i1: 初始为0第一次到达是变成1。加入队列。 1变2的条件新经过的边数等于x1。加入队列。 2不会发生的变化。 每个节点最多入队两次。估计时间复杂度是O(n)。 目的地的i1如果为1则严格第二少的边数为x1否则为x2。
通过边数计算时间 如果总时间time / change 是奇数需要等待 等待时间 change - (time/change)。
代码
核心代码
class CNeiBo2
{
public:CNeiBo2(int n, bool bDirect, int iBase 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase){m_vNeiB.resize(n);}CNeiBo2(int n, vectorvectorint edges, bool bDirect, int iBase 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase){m_vNeiB.resize(n);for (const auto v : edges){m_vNeiB[v[0] - iBase].emplace_back(v[1] - iBase);if (!bDirect){m_vNeiB[v[1] - iBase].emplace_back(v[0] - iBase);}}}inline void Add(int iNode1, int iNode2){iNode1 - m_iBase;iNode2 - m_iBase;m_vNeiB[iNode1].emplace_back(iNode2);if (!m_bDirect){m_vNeiB[iNode2].emplace_back(iNode1);}}const int m_iN;const bool m_bDirect;const int m_iBase;vectorvectorint m_vNeiB;
};class Solution {
public:int secondMinimum(int n, vectorvectorint edges, int time, int change) {CNeiBo2 neiBo(n, edges, false, 1);queuepairint,int que; vectorint vDis(n), vStatu(n);que.emplace(0,0);vStatu[0] 1;while (que.size()){const auto [cur,curDis] que.front();que.pop();for (const auto next : neiBo.m_vNeiB[cur]){const int iNewDis curDis 1;if (0 vStatu[next]){vDis[next] iNewDis;vStatu[next] 1;que.emplace(next,iNewDis);}else if ((1 vStatu[next])( vDis[next]1 iNewDis)){vStatu[next] 2;que.emplace(next, iNewDis);}}}const int iEdgeNum (1 vStatu.back()) ? (vDis.back() 2) : (vDis.back() 1);int iTime 0;for (int i 1; i iEdgeNum; i){iTime time;if ((iTime / change) 1){if (iEdgeNum ! i){iTime (change - (iTime % change));}}}return iTime;}
};测试用例
templateclass T,class T2 void Assert(const T t1, const T2 t2) { assert(t1 t2); }
template void Assert(const vector v1, const vector 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 n, time, change; vectorvector edges; { Solution sln; n 5, edges { {1,2},{1,3},{1,4},{3,4},{4,5} }, time 3, change 5; auto res sln.secondMinimum(n, edges, time, change); Assert(13, res); } { Solution sln; n 2, edges { {1,2} }, time 3, change 2; auto res sln.secondMinimum(n, edges, time, change); Assert(11, res); } }
2023年4月
class Solution { public: int secondMinimum(int n, vectorvector edges, int time, int change) { m_vNeiB.resize(n 1); m_vDis.assign(n 1,INT_MAX); m_vDis2.assign(n 1, INT_MAX); for (const auto e : edges) { m_vNeiB[e[0]].emplace_back(e[1]); m_vNeiB[e[1]].emplace_back(e[0]); } std::queuepairint,int que; que.emplace(1,0); while (que.size()) { const int iCur que.front().first; const int len que.front().second; que.pop(); for (const auto next : m_vNeiB[iCur]) { const int iNewLen len 1; if (iNewLen m_vDis2[next]) { continue; } que.emplace(next, iNewLen); if (iNewLen m_vDis[next]) { m_vDis[next] iNewLen; } else if (iNewLen ! m_vDis[next]) { m_vDis2[next] iNewLen; } } } int tmp m_vDis2[n]; int iRet 0; while (tmp–) { if ((iRet / change) 1) { iRet (change - iRet%change); } iRet time; } return iRet; } vectorvector m_vNeiB; vector m_vDis; vector m_vDis2; }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
