解题思路
这是一个带有状态的最短路问题。可以将每个节点 i 和当前持有的通道类型组合成一个状态 (i,type)，其中 type∈{0,1}（内部用 0 表示题目中的 1 类型，1 表示 2 类型）。使用变种的 Dijkstra 算法 求解：
-
定义 dist[i][0] 表示从起点 1 出发，到达节点 i 且当前通道类型为 1 的最短时间。
dist[i][1] 表示到达节点 i 且当前类型为 2 的最短时间。
-
初始状态：从节点 1 出发，可以任意选择一种通道类型且无切换延迟，因此
dist[1][0]=dist[1][1]=0 ，将两个状态加入优先队列。
题目内容
在一个由 n 个网络节点和 m 条双向链路构成的通信网络中，节点编号 1 到 n。每条链路固定使用两种通道类型之一（类型 1 或类型 2），通过该链路需要花费 w 个单位时间。
每个节点 i 有一个切换延迟 ci。当数据包到达某个节点后，如果接下来要使用的链路通道类型与当前持有的通道类型不同，则必须在该节点花费 ci 的时间完成切换。数据包从节点 1 出发时，可以任意选择一种通道类型且不产生切换延迟；到达目的节点 n 后任务完成，无需再进行切换。
请你计算从节点 1 到节点 n 所需的最短总时间。
数据范围：
- 节点数 n 和链路数 m 满足 1≤n,m≤105。
- 切换延迟 ci 满足 0≤ci≤109。
