给定一个 n 个点 m 条边的不含重边和自环的无向图。 点的编号为 1∼n ,边的编号为 1∼m 。 在 t=0 时刻,你位于 1 号点。 你的任务是尽可能早的抵达 n 号点。 第 i 条边连接点 ai 和点 bi ,通过此边需要花费的时间为 ci 。 在整个移动过程中,你只有在整数时刻才能离开某一点前往另一点。 此外,第 i 个点有 ki 个禁止离开时刻。 在每个点的禁止离开时刻,你无法离开该点前往其它点。 请你计算抵达 n 号点的最早可能时刻。
时间: 2023-04-08 09:00:56 浏览: 242
无向图的计算代码
这是一个算法问题,我可以回答。这个问题可以使用 Dijkstra 算法来解决,具体步骤如下:
1. 初始化一个数组 dist,表示从起点到每个点的最短距离,初始值为无穷大,起点为0。
2. 初始化一个优先队列 q,将起点加入队列中。
3. 当队列不为空时,取出队列中距离起点最近的点 u。
4. 遍历 u 的所有邻居 v,如果从起点到 v 的距离可以通过 u 更新,则更新 dist[v] 的值,并将 v 加入队列中。
5. 如果队列中已经包含了终点 n,则返回 dist[n] 的值,否则继续执行步骤3。
需要注意的是,在每个点的禁止离开时刻,需要将该点从队列中移除,直到禁止离开时刻结束再将其加回队列中。
通过这个算法,可以计算出抵达 n 号点的最早可能时刻。
阅读全文