题目与翻译 1003 Emergency 紧急情况 (25分)
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.
作为一个城市的紧急救援队队长，你会得到一张特殊的国家地图。这张地图显示了由一些道路连接起来的几个零散的城市。每个城市的救援队伍数量以及每一对城市之间的道路长度都在地图上标注出来。当其他城市给你打紧急电话时，你的工作就是带领你的人尽快赶到那个地方，同时，在路上尽可能多的召集人手。
Input Specification: 输入规格:Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (≤500) - the number of cities (and the cities are numbered from 0 to N−1), M - the number of roads, C1 and C2 - the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.
每个输入文件包含一个测试用例。对于每个测试案例，第一行包含4个正整数: n (≤500)-城市数量(城市数量从0到 n-1) ，m-道路数量，c1和 c2-你目前所在的城市和你必须保存的城市。下一行包含 n 个整数，其中 i-th 整数表示第 i 城市救援队的数量。然后是 m 线，每条线描述一条有三个整数 c1，c2和 l 的道路，这三个整数分别是由一条道路连接起来的两个城市和这条道路的长度。它保证至少存在一条从 c1到 c2的路径。
Output Specification: 输出规格:For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.
对于每个测试用例，用一行打印两个数字: c1和 c2之间不同的最短路径的数量，以及您可能召集的救援队伍的最大数量。一行中的所有数字必须正好用一个空格隔开，并且在一行的末尾不允许有额外的空格。
Sample Input: 样本输入: 5 6 0 2 1 2 1 5 3 0 1 1 0 2 2 0 3 1 1 2 1 2 4 1 3 4 1 Sample Output: 示例输出: 2 4 理解与算法城市，道路，路程长度，这几个要素很容易联想到图。
首先我们来定义需要的数据结构：
起始节点到其他各个节点的距离数组，dis，当还无法到达某个节点时，就将这个节点的距离设置为无穷远
起始节点到其他各个节点的最短路径的数量数组，初始值为0，除了到起始节点本身的路径数量为1
起始节点到其他各个节点的能召集的最大救援队数量
起始节点到其他各个节点的访问数组，代表是否访问过这个节点
vector<vector<int>> edge(N, vector<int>(N, INT_MAX)); // 到i顶点的距离 vector<int> dis(N, INT_MAX); // c1和 c2之间不同的最短路径的数量 vector<int> roads(N, 0); // 到i顶点的救援队的数量 vector<int> teams(N, 0); // 是否访问过i顶点 vector<bool> visit(N, false);因为我们有众多的节点需要遍历，所以不可避免地用到循环，确定循环前我们需要知道循环条件，很显然，每个节点至少要访问一次，此处的访问是指访问它的邻接链表，也就是从该点出发能够到达的其他节点。
而后我们还要知道如何找到下一个访问的节点，图并不是线性的，图是网状结构，没有明确的先后关系，理想状态中，***的访问顺序是拓扑序，当一个节点被访问之后就拿掉所有的出边，再去寻找下一个没有入边的节点，理由是这样就不可能出现访问其他节点导致以前的最短路程出现问题。例如下面这个图：
如果从C1出发，先走C2，再走到C4之类的节点就会导致C1-C2这条边不是最短路程，而出现这个问题的原因就是因为直接走C2它的入度并不为0，而是1，因为C3还可以到C2！
但是维护一个入度数组十分复杂，代价较大，我们可以换一种方式，在遍历完一个节点之后我们选择下一个未被访问过的节点中，路程最近的节点，这个节点有可能不是初始节点的邻接节点，这样做的目的就是不可能从起始节点出发经过其他未访问的节点再到这个节点的路程小于当前的路程！