前置知识:最短路径
step1.动画理解Dijstra算法
step2.实现Dijstra算法(C++/Python)
题面描述:
有两个相邻的国家 A 和 B，其中有 N 个城市，编号为 1 到 N。M 条公路连接这些城市，其中有些是国内公路，有些是连接 A 国与 B 国边界城市的跨国公路。每条公路有一个距离和花费。
P2277.第2题-到邻国城市的最短距离
题目内容
A 国与 B 国是相邻的两个国家，每个国家都有很多城市，国家内部有很多连接城市的公路，国家之间也有很多跨国公路，连接两个国家的边界城市。
两个国家一共有 N 个城市，编号 1 到 N ，一共有 M 条公路，包括国内公路与跨国公路。
小明生活在 A 国的城市 1（即编号为1的城市），想去 B 国的城市 N 游玩，由于小明办理的只能入境一次的签证，所以从城市 1 到城市 N 的路径中，只能通过一条跨国公路。
每条公路都一个距离，并且通过这条公路会有一个花费。
请帮小明计算出城市 1 到城市 N 的最短距离，并在距离最短的前提下，再计算出最少花费。
如果无法到达城市 N ，输出 −1 。
输入描述
- 第一行是一个整数 N，表示两个国家的城市数量。
- 第二行是一个整数 M，表示两个国家的公路数量，包括国内公路与跨国公路。
- 第三行是一个长度为 N 的字符串，字符串第 i 个（从1开始计数）字符为 A 或 B，表示城市 i 属于 A 国或 B 国，其中第 1 个字符一定为 A，第 N 个字符一定为 B。
- 最后是 M 行，每行包含 4 个整数 U、V、W、C，表示编号为 U 的城市与编号为 V 的城市之间有一条公路，长度是 W，花费是 C。
- 注意：所有公路都是双向的，且两个城市之间最多只有一条公路。
数据范围
2≤N≤1000，
0≤M≤50000，
1≤U,V≤N，
1≤W≤500。
输出描述
输出从城市1到城市N的最短距离，并在距离最短的前提下，再输出最少花费。
如果无法到达城市N，输出−1。
样例1
输入
5
5
AABBB
3 1 200 1
2 3 150 3
5 2 160 5
4 3 170 7
4 5 170 9
输出
540 17
说明
可以找到一条最优线路：城市1(A国) -> 城市3(B国) -> 城市4(B国) -> 城市5(B国)，
而且只通过一条跨国公路：城市1->城市3，
距离=200+170+170=540
花费=1+7+9=17
样例2
输入
6
7
AAABBB
1 2 150 2
1 3 100 2
1 4 160 1
2 6 150 5
3 5 100 3
4 6 160 1
5 6 100 4
输出
300 7
说明
可以找到一条最优线路：城市1(A国) -> 城市2(B国) -> 城市6(B国) ，
而且只通过一条跨国公路：城市1->城市2，
距离=150+150=300
花费=2+5=7
另外一条线路：1->3->5->6虽然距离也是300，
但是花费是2+3+4=9>7，所有不是最优线路
样例3
输入
4
3
ABAB
1 2 100 2
2 3 40 3
3 4 50 6
输出
-1
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
