问题描述

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

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

思路

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)$