久違的PAT，由于考研408數(shù)據結構中有一定需要，同時也是對先前所遺留的競賽遺憾進行一定彌補 ，再次繼續(xù)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條路進行連接且有一定數(shù)量的救援人員，C1是初始地點，C2是目的地。

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

　　　　　　第二行是：各城市所包含的救援人數(shù)（共N個數(shù)據）

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

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

題目分析

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

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

個人想法

　　　　那么首先對于變量的設置

1 int N, M, C1, C2;//題目所給城市數(shù)量、路徑數(shù)量、初始地、目的地
2 int c1, c2, l, dis[501][501];//二維數(shù)組dis用于記錄我們所輸入的M行中地點1和地點2之間的距離l3 int paths, teams;//輸出的兩個結果：路徑數(shù)，人員數(shù)
4 int mindis[501];//計算過程中記錄某條路勁上的當前最短路徑
5 int* cteam;//各城市的救援人數(shù)，這里其實是個數(shù)組，寫成指針是為了方便在主函數(shù)中進行內存管理malloc和初始化memset

　　　　我在此均設為全局變量，因為在后續(xù)的編寫中我發(fā)現(xiàn)會單獨寫出一個dfs函數(shù)，而用全局變量可以更容易調用。要清楚設為數(shù)組的條件是記錄多條數(shù)據，再次如城市是否連接，各城市間的路徑長度，各城市的救援人數(shù)，遍歷每條路徑所需要的各路徑總長度（涉及比較和有下標組成的路徑標識，所以需要數(shù)組記錄，單純的變量無法做到），其次對于函數(shù)的中間變量我采取即寫即設，并沒有在開始就盡可能將其完全想到。

　　　　然后編寫數(shù)據的輸入和輸出。

1 //初始化dis數(shù)組，不相連的無窮大距離，自身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數(shù)，初始為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用于存放某條路徑的長度，設為一個無窮大的是為了在后續(xù)比較中讓我們所輸入的“非無窮大”的距離記錄并比較
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//換句話說，如果這里初始為0，那么往后輸入、記錄的每條有效路徑的長度都會大于0，從而導致最短路徑無法更新

20     dfs(C1, 0, cteam[C1]);//深度遍歷函數(shù)
21     printf("%d %d", paths, teams);

?文章來源地址http://www.zghlxwxcb.cn/news/detail-412537.html

　　　　接下來就是dfs函數(shù)的編寫，在次先回答分析階段的幾個問題。

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

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

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

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

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

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

 1 void dfs(int curcity, int curlen, int curteam) {//每次傳入節(jié)點，路徑長，隊伍人員
 2     if (curlen > mindis[curcity])return;　　　　　　//如果比該節(jié)點所記錄的最短路徑要短，直接退出
 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;　　　　//不大于當前最短路徑時，更新最短節(jié)點　　
17         for (int i = 0; i < 501; i++) {
18             if (dis[curcity][i] != 9999999 && i != curcity)　　　　　　//遍歷每個節(jié)點，同時選擇有效路徑進行迭代
19                 dfs(i, curlen + dis[curcity][i], curteam + cteam[i]);//疊加路徑長度和人員數(shù)量
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數(shù)組，不相連的無窮大距離，自身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數(shù)
    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;
}

View Code

最后最后

?

?我自己的VS2022多次實驗是沒有問題的，但是PAT就。。。。

?

多次調試甚至結果都沒有，只是提醒scanf出現(xiàn)return問題，反復看了很多次無解，就很無奈。。。在此還是希望各位看官可以幫我找找問題并指正，不勝感激！

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

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define inf 1e8
 4 #define max 500 
 5 int t = inf;
 6 int  den = 0, maxN = 0;//den:不同路徑數(shù), maxN:最大救援數(shù)
 7 int mat[max][max];//節(jié)點之間的權值 
 8 int city[max];//各節(jié)點救援隊數(shù) 
 9 int v[max];//記錄節(jié)點是否已經被訪問 
10 int n, m, c1, c2;
11 void dfs(int c1, int c2, int dist, int num);//初始節(jié)點（中間節(jié)點），目標節(jié)點，權值，救援隊數(shù)量 
12 int main() {
13     scanf("%d %d %d %d", &n, &m, &c1, &c2);
14     memset(v, 0, n);
15     for (int i = 0; i < n; ++i) {
16         scanf("%d", &city[i]);
17     }
18     for (int i = 0; i < n; ++i) {
19         for (int j = 0; j < n; ++j) {
20             mat[i][j] = inf;
21         }
22     }
23     for (int i = 0; i < m; ++i) {
24         int start, end, len;
25         scanf("%d %d %d", &start, &end, &len);
26         mat[start][end] = mat[end][start] = len;
27     }
28     dfs(c1, c2, 0, city[c1]);
29     printf("%d %d", den, maxN);
30     return 0;
31 } 
32 void dfs(int c1, int c2, int dist, int num) {
33     
34     if (c1 == c2) {
35         if (dist < t){
36             den = 1;
37             t = dist;
38             maxN = num;
39         }
40         else if (dist == t) {
41             den++;
42             if (maxN < num) maxN = num;
43         }
44         return ;
45     }
46     if (dist > t) return ;//剪枝 
47     
48     
49     for(int i = 0; i < n; ++i) {
50         if (!v[i] && mat[c1][i] != inf) {
51             v[i] = 1;
52             dfs(i, c2, dist+mat[c1][i], num+city[i]);
53             v[i] = 0;
54         }
55     }
56 }

View Code

附贈大佬的滿分代碼，僅供參考。

<------------------------------- 更新?------------------------------->

　　　　在上述大佬的滿分代碼中，我仔細觀察、理解后并未發(fā)現(xiàn)我的錯誤，只是其中在迭代的部分出現(xiàn)了以下代碼

1  if (!v[i] && mat[c1][i] != inf) {
2             v[i] = 1;//標記為經過此節(jié)點
3             dfs(i, c2, dist+mat[c1][i], num+city[i]);
4             v[i] = 0;//標記回未經過此節(jié)點
5         }

　　　　多數(shù)的參考代碼中均提到了這種標記數(shù)組，但是筆者先前認為minidis數(shù)組不僅可以記錄最小距離也能兼?zhèn)錁擞浀淖饔?，于是沒有改正。但在學習深度遍歷和廣度遍歷的時候，看到了一篇文章，其中的圖解讓我茅塞頓開，深度遍歷在無向圖中的每條路徑是沒走完的！尤其再次提醒我經常遺忘、糊涂的一點，遞歸是需要返回的！ 而如同圖中顯示的一樣，在返回的過程中，先前的節(jié)點無論是采用我所寫的mnidis數(shù)組還是多數(shù)寫法用到的標記數(shù)組，都因為標記了經過此節(jié)點而在返回的過程中被掠過，導致更多的路線為別探尋，也就少了更多可能，這點在于廣度優(yōu)先遍歷對比極為明顯。

?

　　所以對原有的代碼只需添加一個標記數(shù)組，并在循環(huán)遞歸前標為經過，遞歸后還原即可。

總結

　　　　第三題從某種意義來說是真正需要思考的題目，考的雖然是圖，但還是很簡單的一種，對于此題，無它，看懂圖，理清每條思路即可，有必要說的是，對于競賽也好，Leecode和洛也好，c的問題貌似總是大于c++的，也不知道現(xiàn)在改c++還能不能來的及。。。

　　　　感謝您能看到這，菜鳥記錄，挑戰(zhàn)每種錯誤的極限！

?

到了這里，關于菜鳥記錄：c語言實現(xiàn)PAT甲級1003--Emergency的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！