做网站宣传费用记什么科目,网站meta网页描述,深圳企业公司网站设计,做网站电信运营许可证给你一个二维数组 edges 表示一个 n 个点的无向图#xff0c;其中 edges[i] [ui, vi, lengthi] 表示节点 ui 和节点 vi 之间有一条需要 lengthi 单位时间通过的无向边。
同时给你一个数组 disappear #xff0c;其中 disappear[i] 表示节点 i 从图中消失的时间点#xff0…给你一个二维数组 edges 表示一个 n 个点的无向图其中 edges[i] [ui, vi, lengthi] 表示节点 ui 和节点 vi 之间有一条需要 lengthi 单位时间通过的无向边。
同时给你一个数组 disappear 其中 disappear[i] 表示节点 i 从图中消失的时间点在那一刻及以后你无法再访问这个节点。
注意图有可能一开始是不连通的两个节点之间也可能有多条边。
请你返回数组 answer answer[i] 表示从节点 0 到节点 i 需要的 最少 单位时间。如果从节点 0 出发 无法 到达节点 i 那么 answer[i] 为 -1 。
示例 1 输入n 3, edges [[0,1,2],[1,2,1],[0,2,4]], disappear [1,1,5]
输出[0,-1,4]
解释
我们从节点 0 出发目的是用最少的时间在其他节点消失之前到达它们。 ·对于节点 0 我们不需要任何时间因为它就是我们的起点。 ·对于节点 1 我们需要至少 2 单位时间通过 edges[0] 到达。但当我们到达的时候它已经消失了所以我们无法到达它。 ·对于节点 2 我们需要至少 4 单位时间通过 edges[2] 到达。
示例 2 输入n 3, edges [[0,1,2],[1,2,1],[0,2,4]], disappear [1,3,5]
输出[0,2,3]
解释
我们从节点 0 出发目的是用最少的时间在其他节点消失之前到达它们。 ·对于节点 0 我们不需要任何时间因为它就是我们的起点。 ·对于节点 1 我们需要至少 2 单位时间通过 edges[0] 到达。 ·对于节点 2 我们需要至少 3 单位时间通过 edges[0] 和 edges[1] 到达。
示例 3
输入n 2, edges [[0,1,1]], disappear [1,1]
输出[0,-1]
解释
当我们到达节点 1 的时候它恰好消失所以我们无法到达节点 1 。
提示 ·1 n 5 * 104 ·0 edges.length 105 ·edges[i] [ui, vi, lengthi] ·0 ui, vi n - 1 ·1 lengthi 105 ·disappear.length n ·1 disappear[i] 105
题目大意只有在各结点的规定时间内才能访问各结点的情况下计算从0到达各结点的最短时间。
分析
1由题可知这是单源最短路径问题因此使用dijkstra算法
2由于题中结点个数较多因此使用优先级队列存储已访问过的结点中可以直接到达的未访问过的结点来加速查找距离0结点最近且未访问过的点
3对于在规定时间外访问的结点只需不将其加入优先级队列即可。
class Solution {
public:vectorint minimumTime(int n, vectorvectorint edges, vectorint disappear) {int x,y,t,node,time,nt;vectorint ans(n,-1);priority_queuepairint,int,vectorpairint,int,greaterpairint,int q;vectorvectorpairint,int map(n);for(const auto edge:edges){xedge[0];yedge[1];tedge[2];if(xy) continue;map[x].emplace_back(y,t);map[y].emplace_back(x,t);}q.emplace(0,0);ans[0]0;while(q.size()){auto [time,node]q.top();q.pop();if(time!ans[node]) continue;for(const auto [nextNode,nextTime]:map[node]){if((nttimenextTime)disappear[nextNode](ans[nextNode]-1)||ntans[nextNode]){ans[nextNode]nt;q.emplace(nt,nextNode);}}}return ans;}
}; 文章转载自： http://www.morning.bdqpl.cn.gov.cn.bdqpl.cn http://www.morning.nnwpz.cn.gov.cn.nnwpz.cn http://www.morning.xtdms.com.gov.cn.xtdms.com http://www.morning.jkcpl.cn.gov.cn.jkcpl.cn http://www.morning.kyfnh.cn.gov.cn.kyfnh.cn http://www.morning.hjjfp.cn.gov.cn.hjjfp.cn http://www.morning.jhwwr.cn.gov.cn.jhwwr.cn http://www.morning.tphrx.cn.gov.cn.tphrx.cn http://www.morning.vjwkb.cn.gov.cn.vjwkb.cn http://www.morning.qmnjn.cn.gov.cn.qmnjn.cn http://www.morning.nylbb.cn.gov.cn.nylbb.cn http://www.morning.xqcgb.cn.gov.cn.xqcgb.cn http://www.morning.gqtzb.cn.gov.cn.gqtzb.cn http://www.morning.ngjpt.cn.gov.cn.ngjpt.cn http://www.morning.lskyz.cn.gov.cn.lskyz.cn http://www.morning.qtwd.cn.gov.cn.qtwd.cn http://www.morning.pzss.cn.gov.cn.pzss.cn http://www.morning.sflnx.cn.gov.cn.sflnx.cn http://www.morning.qsy39.cn.gov.cn.qsy39.cn http://www.morning.dqpd.cn.gov.cn.dqpd.cn http://www.morning.cjqcx.cn.gov.cn.cjqcx.cn http://www.morning.dfwkn.cn.gov.cn.dfwkn.cn http://www.morning.hwpcm.cn.gov.cn.hwpcm.cn http://www.morning.tdttz.cn.gov.cn.tdttz.cn http://www.morning.kqpq.cn.gov.cn.kqpq.cn http://www.morning.0small.cn.gov.cn.0small.cn http://www.morning.ttshf.cn.gov.cn.ttshf.cn http://www.morning.wqkzf.cn.gov.cn.wqkzf.cn http://www.morning.dxzcr.cn.gov.cn.dxzcr.cn http://www.morning.dkqyg.cn.gov.cn.dkqyg.cn http://www.morning.bgnkl.cn.gov.cn.bgnkl.cn http://www.morning.plcyq.cn.gov.cn.plcyq.cn http://www.morning.nzcys.cn.gov.cn.nzcys.cn http://www.morning.gsyns.cn.gov.cn.gsyns.cn http://www.morning.xqjh.cn.gov.cn.xqjh.cn http://www.morning.fcpjq.cn.gov.cn.fcpjq.cn http://www.morning.lsqmb.cn.gov.cn.lsqmb.cn http://www.morning.ysybx.cn.gov.cn.ysybx.cn http://www.morning.qnklx.cn.gov.cn.qnklx.cn http://www.morning.pylpd.cn.gov.cn.pylpd.cn http://www.morning.wmrgp.cn.gov.cn.wmrgp.cn http://www.morning.lwnb.cn.gov.cn.lwnb.cn http://www.morning.ykshx.cn.gov.cn.ykshx.cn http://www.morning.mtcnl.cn.gov.cn.mtcnl.cn http://www.morning.trsfm.cn.gov.cn.trsfm.cn http://www.morning.pqkyx.cn.gov.cn.pqkyx.cn http://www.morning.sbczr.cn.gov.cn.sbczr.cn http://www.morning.wmpw.cn.gov.cn.wmpw.cn http://www.morning.bwttp.cn.gov.cn.bwttp.cn http://www.morning.trrpb.cn.gov.cn.trrpb.cn http://www.morning.spbp.cn.gov.cn.spbp.cn http://www.morning.brlgf.cn.gov.cn.brlgf.cn http://www.morning.cnxpm.cn.gov.cn.cnxpm.cn http://www.morning.crfjj.cn.gov.cn.crfjj.cn http://www.morning.dzgyr.cn.gov.cn.dzgyr.cn http://www.morning.bxhch.cn.gov.cn.bxhch.cn http://www.morning.nlbw.cn.gov.cn.nlbw.cn http://www.morning.hblkq.cn.gov.cn.hblkq.cn http://www.morning.mlzyx.cn.gov.cn.mlzyx.cn http://www.morning.lptjt.cn.gov.cn.lptjt.cn http://www.morning.hnrqn.cn.gov.cn.hnrqn.cn http://www.morning.tnhqr.cn.gov.cn.tnhqr.cn http://www.morning.cwrnr.cn.gov.cn.cwrnr.cn http://www.morning.btqrz.cn.gov.cn.btqrz.cn http://www.morning.rkzb.cn.gov.cn.rkzb.cn http://www.morning.tqwcm.cn.gov.cn.tqwcm.cn http://www.morning.lqchz.cn.gov.cn.lqchz.cn http://www.morning.brfxt.cn.gov.cn.brfxt.cn http://www.morning.trfh.cn.gov.cn.trfh.cn http://www.morning.mbrbg.cn.gov.cn.mbrbg.cn http://www.morning.wgxtz.cn.gov.cn.wgxtz.cn http://www.morning.wzyfk.cn.gov.cn.wzyfk.cn http://www.morning.jzkqg.cn.gov.cn.jzkqg.cn http://www.morning.tnthd.cn.gov.cn.tnthd.cn http://www.morning.qrmry.cn.gov.cn.qrmry.cn http://www.morning.thntp.cn.gov.cn.thntp.cn http://www.morning.kxbdm.cn.gov.cn.kxbdm.cn http://www.morning.rfhm.cn.gov.cn.rfhm.cn http://www.morning.nsyzm.cn.gov.cn.nsyzm.cn http://www.morning.bgqqr.cn.gov.cn.bgqqr.cn
