1000ms

Difficulty: 8

所属公司 : 腾讯

时间 :2024年3月30日

算法与标签>最短路算法

会员专享

请先登录，开通会员或购买该题目所属题库（腾讯机考题库），可解锁完整内容。

购买题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（腾讯机考题库），可解锁完整内容。

购买题库开通会员

思路

Dijkstra算法的变种

dist[i][0] 表示从 1 到 i ，到达 i 的时候，使用第一种交通工具的最小花费
dist[i][1] 表示从 1 到 i ，到达 i 的时候，使用第二种交通工具的最小花费最终答案就是 min(dist[n][0], dist[n][1])

主要考察对于 Dijkstra 算法是否熟悉，注意这里使用的是小根堆

时间复杂度： $O(m\log n)$

问题描述

小红是一位热衷旅游的程序员。他所在的国家共有 $n$ 个城市,编号从 $1$ 到 $n$ 。这些城市之间有 $m$ 条双向的交通线路,分别为飞机线路和火车线路。小红起始位于编号为 $1$ 的城市,他计划前往编号为 $n$ 的城市进行旅游。

在这个国家,每个城市都有一个固定的时间 $a_i$ ,表示在该城市中转换交通工具所需的时间。特别地,在出发城市 $1$ 和目的地城市 $n$ ,小红不需要转换交通工具。