久违的PAT，由于考研408数据结构中有一定需要，同时也是对先前所遗留的竞赛遗憾进行一定弥补 ，再次继续PAT甲级1003.。

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?.

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.

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

　　　就是说一个救援队，在地图所给N个的城市里进行救援，每个城市之间有M条路进行连接且有一定数量的救援人员，C1是初始地点，C2是目的地。

　　所需输入第一行是：城市数量、路径数量、初始地、目的地

　　　　　　第二行是：各城市所包含的救援人数（共N个数据）

　　　　　　接下来的M行：地点1、地点2、1,2间的距离L

　　所得输出：最短路径的数量、最多得到的救援人数

题目分析

　　　　一眼图的遍历，那么能用到的方法很多，例如广度优先、深度优先、迪杰斯特拉等等，笔者在此用深度优先，迪杰斯特拉等“高级”算法往后更新。

　　　　要清楚整体大概思路：首先对数值进行输入，对于数组，初始化应是尽可能大还是尽可能小？然后深度遍历各节点时，如何遍历下去的条件是什么？如何选择路径，到达目的地之前应该怎么进入下一个节点？达到目的地后，如何判断是最小路径？如何记录和比较最多救援人数？

个人想法

　　　　那么首先对于变量的设置

int N, M, C1, C2;//题目所给城市数量、路径数量、初始地、目的地
int c1, c2, l, dis[501][501];//二维数组dis用于记录我们所输入的M行中地点1和地点2之间的距离l3 int paths, teams;//输出的两个结果：路径数，人员数
4 int mindis[501];//计算过程中记录某条路劲上的当前最短路径
5 int* cteam;//各城市的救援人数，这里其实是个数组，写成指针是为了方便在主函数中进行内存管理malloc和初始化memset

　　　　我在此均设为全局变量，因为在后续的编写中我发现会单独写出一个dfs函数，而用全局变量可以更容易调用。要清楚设为数组的条件是记录多条数据，再次如城市是否连接，各城市间的路径长度，各城市的救援人数，遍历每条路径所需要的各路径总长度（涉及比较和有下标组成的路径标识，所以需要数组记录，单纯的变量无法做到），其次对于函数的中间变量我采取即写即设，并没有在开始就尽可能将其完全想到。

　　　　然后编写数据的输入和输出。

1 //初始化dis数组，不相连的无穷大距离，自身0距离or-1？，表示距离的同时表示有无连接 
2 for (int i = 0; i < 501; i++) 
3 for (int j = 0; j < 501; j++)
 4     if (i == j)dis[i][j] = 0;//自身距离
 5        else
 6         dis[i][j] = 9999999;//设为无穷大
 7    
 8     scanf("%d%d%d%d", &N, &M, &C1, &C2);

 9     cteam = malloc(sizeof(int) * 4);
10     memset(cteam, 0, sizeof(cteam) * 4);//记录每个城市的team数，初始为0个救援人员
11     for (int i = 0; i < N; i++) {
12         scanf("%d", &cteam[i]);　　
13     }
14     for (int i = 0; i < M; i++) {
15         scanf("%d%d%d", &c1, &c2, &l);
16         dis[c1][c2] = l;　　　　
17         dis[c2][c1] = l;　　　　//无向图，c1->c2==c2->c1，所以两个距离相等
18     }
19     for (int i = 0; i < 501; i++)mindis[i] = 9999999;　　//需要注意的是这里mindis用于存放某条路径的长度，设为一个无穷大的是为了在后续比较中让我们所输入的“非无穷大”的距离记录并比较
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//换句话说，如果这里初始为0，那么往后输入、记录的每条有效路径的长度都会大于0，从而导致最短路径无法更新

20     dfs(C1, 0, cteam