题目内容

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

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

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

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

前置知识:最短路径

step1.动画理解Dijstra算法

step2.实现Dijstra算法(C++/Python)

题面描述:

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