前置知识:最短路径

题面描述:

有两个相邻的国家 $A$ 和 $B$ ，其中有 $N$ 个城市，编号为 $1$ 到 $N$ 。 $M$ 条公路连接这些城市，其中有些是国内公路，有些是连接 $A$ 国与 $B$ 国边界城市的跨国公路。每条公路有一个距离和花费。

1000ms

Difficulty: 9

所属公司 : 华为

算法与标签>最短路算法

$A$ 国与 $B$ 国是相邻的两个国家，每个国家都有很多城市，国家内部有很多连接城市的公路，国家之间也有很多跨国公路，连接两个国家的边界城市。

两个国家一共有 $N$ 个城市，编号 $1$ 到 $N$ ，一共有 $M$ 条公路，包括国内公路与跨国公路。

小明生活在 $A$ 国的城市 $1$ （即编号为 $1$ 的城市），想去 $B$ 国的城市 $N$ 游玩，由于小明办理的只能入境一次的签证，所以从城市 $1$ 到城市 $N$ 的路径中，只能通过一条跨国公路。

每条公路都一个距离，并且通过这条公路会有一个花费。

编辑器加载中…

输入

预期输出（选填）