前置知识:最短路径

step1.动画理解Dijstra算法

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

题面描述:

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

题目内容

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

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

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

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

请帮小明计算出城市 $1$ 到城市 $N$ 的最短距离，并在距离最短的前提下，再计算出最少花费。

如果无法到达城市 $N$ ，输出 $-1$ 。

输入描述

1. 第一行是一个整数 $N$，表示两个国家的城市数量。
2. 第二行是一个整数 $M$，表示两个国家的公路数量，包括国内公路与跨国公路。
3. 第三行是一个长度为 $N$ 的字符串，字符串第 $i$ 个（从$1$开始计数）字符为 $A$ 或 $B$，表示城市 $i$ 属于 A 国或 B 国，其中第 $1$ 个字符一定为 $A$，第 $N$ 个字符一定为 $B$。
4. 最后是 $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