思路
Dijkstra算法的变种
- dist[i][0] 表示从 1 到 i ，到达 i 的时候，使用第一种交通工具的最小花费
- dist[i][1] 表示从 1 到 i ，到达 i 的时候，使用第二种交通工具的最小花费
最终答案就是 min(dist[n][0], dist[n][1])
主要考察对于 Dijkstra 算法是否熟悉，注意这里使用的是小根堆
时间复杂度：O(mlogn)
P1778.2024.03.30-第四题-小红的环游之旅
问题描述
小红是一位热衷旅游的程序员。他所在的国家共有 n 个城市,编号从 1 到 n。这些城市之间有 m 条双向的交通线路,分别为飞机线路和火车线路。小红起始位于编号为 1 的城市,他计划前往编号为 n 的城市进行旅游。
在这个国家,每个城市都有一个固定的时间 ai,表示在该城市中转换交通工具所需的时间。特别地,在出发城市 1 和目的地城市 n,小红不需要转换交通工具。
小红可以自由选择乘坐飞机或火车前往下一个城市。他希望能够以最短的时间从出发城市抵达目的地城市。
输入格式
第一行包含两个正整数 n 和 m,分别表示城市数量和交通线路数量。
第二行包含 n 个正整数 a1,a2,…,an,表示每个城市中转换交通工具所需的时间。
接下来 m 行,每行包含四个正整数 u,v,w,t,其中 u 和 v 表示线路连接的两个城市编号, w 表示沿该线路行驶所需的时间, t 的值为 1 表示该线路为飞机线路,值为 2 表示该线路为火车线路。
1≤n,m≤105
0≤ai≤109
1≤u,v≤n,1≤w≤109,1≤t≤2
输出格式
输出一个整数,表示小红从出发城市到达目的地城市所需的最短时间。
样例输入
3 3
1 1 1
1 2 1 1
2 3 1 2
2 3 1 2
样例输出
3
样例解释
小红可以按照以下路线行进:
- 从城市 1 乘坐飞机前往城市 2,耗时 1 个单位时间。
- 在城市 2 中转换交通工具,耗时 1 个单位时间。
- 从城市 2 乘坐火车前往城市 3,耗时 1 个单位时间。
总共耗时 3 个单位时间,无法再缩短时间。
评测数据与规模
对于所有评测用例,满足 1≤n,m≤105,0≤ai≤109,1≤u,v≤n,w∈{1,2},1≤w≤109。保证任意两个城市之间是连通的。
