　　久違的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:

Sample Output:

2 4

　　　就是說一個救援隊，在地圖所給N個的城市里進行救援，每個城市之間有M條路進行連接且有一定數量的救援人員，C1是初始地點，C2是目的地，

　　所需輸入第一行是：城市數量、路徑數量、初始地、目的地

　　　　　　第二行是：各城市所包含的救援人數（共N個資料）

　　　　　　接下來的M行：地點1、地點2、1,2間的距離L

　　所得輸出：最短路徑的數量、最多得到的救援人數

題目分析

　　　　一眼圖的遍歷，那么能用到的方法很多，例如廣度優先、深度優先、迪杰斯特拉等等，筆者在此用深度優先，迪杰斯特拉等“高級”演算法往后更新，

　　　　要清楚整體大概思路：首先對數值進行輸入，對于陣列，初始化應是盡可能大還是盡可能小？然后深度遍歷各節點時，如何遍歷下去的條件是什么？如何選擇路徑，到達目的地之前應該怎么進入下一個節點？達到目的地后，如何判斷是最小路徑？如何記錄和比較最多救援人數？

個人想法

　　　　那么首先對于變數的設定

1 int N, M, C1, C2;//題目所給城市數量、路徑數量、初始地、目的地
2 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[C1]);//深度遍歷函式
21     printf("%d %d", paths, teams);

　　　　接下來就是dfs函式的撰寫，在次先回答分析階段的幾個問題，

　　深度遍歷各節點時，如何遍歷下去的條件是什么？

　　條件就是我們的答案，即最短路徑（這里沒加上最多人數是因為得到最多人數的前提是所得的最短路徑存在），所以應該滿足當前所走的路徑curlen小于目前為止該地的最短路徑mindis[curcity]，到這其實也發現mindis陣列不僅記錄到該節點有無被訪問，也記錄歷來被訪問時所經歷的最短路徑！所以如果大于mindis，那么說明這條路徑肯定不是最短，可以直接回傳到上一個路徑并重新選擇路線；反之就繼續遍歷，

　　如何選擇路徑，到達目的地之前應該怎么進入下一個節點？

　　筆者個人對于這種所需函式相同，且需要記錄的題目總是會想到迭代，大部分時候都是管用的，所以在此就是不斷迭代，每次迭代下一個位置的節點、目前所走長度curlen+當前與下一個節點的距離dis、目前所有人員數+下一個節點所有人員數，

　　達到目的地后，如何判斷是最小路徑？如何記錄和比較最多救援人數？

　　該路徑目前的長度curlen是否與目標地的mindis相同，（第一次遍歷的時候應是不同）不同時，將path歸為1，記錄當前team人數，并將此時的curlen視為最短路徑對目標地的mindis賦值；相同時，path++，比較并記錄最新的最多人數，這里指出 必須分為不同或相同的情況，不可以大于或小于 --> path在此時總是歸為1，因為如果大于mindis只會存在第一次到達目的地時mindis初始無窮大的狀態，后續在抵達，如果有比第一次到達路徑長的情況會在往次迭代被終止；如果小于，那么最短路徑和數量就會更新，path歸為1，

 1 void dfs(int curcity, int curlen, int curteam) {//每次傳入節點，路徑長，隊伍人員
 2     if (curlen > mindis[curcity])return;　　　　　　//如果比該節點所記錄的最短路徑要短，直接退出
 3     if (curcity == C2) {　　　　　　　　　　　　　　　　//到達目的地，并判斷是否是最短路徑
 4         if (curlen != mindis[curcity]) {　　　　　　//是最新的最短路徑
 5             paths = 1;
 6             mindis[C2] = curlen;
 7             teams = curteam;
 8         }
 9         else {　　　　　　　　　　　　　　　　　　　　　　//相同的最短路徑
10             paths++;
11             if (curteam > teams)teams = curteam;
12         }
13     }
14     else
15     {
16         if (curlen < mindis[curcity])mindis[curcity] = curlen;　　　　//不大于當前最短路徑時，更新最短節點　　
17         for (int i = 0; i < 501; i++) {
18             if (dis[curcity][i] != 9999999 && i != curcity)　　　　　　//遍歷每個節點，同時選擇有效路徑進行迭代
19                 dfs(i, curlen + dis[curcity][i], curteam + cteam[i]);//疊加路徑長度和人員數量
20         }
21     }
22 }

<-----------------------------------完整代碼----------------------------------->

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int N, M, C1, C2;
int c1, c2, dis[501][501];
int l;
int paths, teams;
int mindis[501];
int* cteam;
void dfs(int curcity, int curlen, int curteam) {
    if (curlen > mindis[curcity])return;
    if (curcity == C2) {
        if (curlen != mindis[curcity]) {
            paths = 1;
            mindis[C2] = curlen;
            teams = curteam;
        }
        else {
            paths++;
            if (curteam > teams)teams = curteam;
        }
    }
    else
    {
        if (curlen < mindis[curcity])mindis[curcity] = curlen;
        for (int i = 0; i < 501; i++) {
            if (dis[curcity][i] != 9999999 && i != curcity)
                dfs(i, curlen + dis[curcity][i], curteam + cteam[i]);
        }
    }
}

int main() {
    //初始化dis陣列，不相連的無窮大距離，自身0距離or-1？
    for (int i = 0; i < 501; i++)
        for (int j = 0; j < 501; j++)
            if (i == j)dis[i][j] = 0;
            else
                dis[i][j] = 9999999;//設為無窮大
   
    scanf("%d%d%d%d", &N, &M, &C1, &C2);
    cteam = malloc(sizeof(int) * 4);
    memset(cteam, 0, sizeof(cteam) * 4);//記錄每個城市的team數
    for (int i = 0; i < N; i++) {
        scanf("%d", &cteam[i]);
    }
    for (int i = 0; i < M; i++) {
        scanf("%d%d%d", &c1, &c2, &l);
        dis[c1][c2] = l;
        dis[c2][c1] = l;
    }
    for (int i = 0; i < 501; i++)mindis[i] = 9999999;
    dfs(C1, 0, cteam[C1]);
    printf("%d %d", paths, teams);
    return 0;
}