久違的PAT，由於考研408數據結構中有一定需要，同時也是對先前所遺留的競賽遺憾進行一定彌補，再次繼續PAT甲級1003.。 As an emergency rescue team leader of a city, you are given a special map of your coun ...

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

Output Specification:

For each test case, print in one line two numbers: the number of different shortest paths between

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;
}