PAT 甲級 1003 Emergency (DFS+最短路徑)(c++版)(附代碼注釋)（附題意分析）

1003 Emergency （25 分）

原文連結：http://kakazai.cn/index.php/Kaka/Pat/query/id/93

文章目錄

• 題目
• 題意分析
• 知識點與坑點
• 一、DFS
• • 算法思路
  • 代碼-c++版
  • 代碼-python版

題目

題目連結：https://pintia.cn/problem-sets/994805342720868352/problems/994805523835109376

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
           

題意分析

• 題意

現在有一個城市群，某些城市之前有路徑，路徑長短不一。每個城市都有救援人員數。現在給定起點城市和終點城市，要求從起點城市出發，以最短的距離到達終點城市，這樣的最短路徑有多少條？最短路徑中，救援人數的最大值是多少？

• 分析

将城市看成點，路徑看成邊。用深度周遊求出從起點到終點所有可能的路徑，取其最小值。同時，在最短路徑中，記錄救援人數的最大值。

知識點與坑點

• 知識點

1）DFS

• 坑點

1）

一、DFS

算法思路

1 從起點出發，用DFS求出到終點所有可能的路徑。要注意，在具體的某條路徑上，為了避免形成環，每個點隻能通路一次。但在不同路徑上，有些點是可以不止一次通路的。

2 周遊的同時，要儲存好每條路徑的總長度，和總救援人數。

3 不斷更新最短路徑，最短路徑數目，總救援人數最大值，并按要求輸出

代碼-c++版

#include<cstdio>
using namespace std;
const int maxn = 510;//圖中，所有點的編号範圍
const int INF = 1000000000;

/* 關鍵變量 */ 
int edge[maxn][maxn];//邊的長度
int v[maxn];//記錄點是否被通路過
int men[maxn];//點的屬性:救緩人數 
int s, d;//s出發，到d去
int n,e;//頂點數，邊數

/*DFS：從起點出發，周遊所有可能的路徑，到達終點*/ 
int shortest_length = INF;  //最短路徑的長度
int shortest_num = 1;	//最短路徑的數量 
int max_men = 0;	//最多救援人員數 
void DFS(int cur, int cur_length, int cur_men) {
//cur=目前路徑上的終點；cur_length = 目前路徑的長度；cur_men = 目前路徑的救援人員數 

  /*剪枝*/
  if (cur_length > shortest_length)return; //目前路徑長度已經大于最短路徑，結束周遊 
  
  /*從起點到終點的路徑*/
  if (cur == d) {	//到達終點d
    if (cur_length < shortest_length) {	//目前路徑更短 
      shortest_length = cur_length;	//更新最短路徑長度 
      shortest_num = 1;	//更新最短路徑數目 
      max_men = cur_men;	//更新救援人數 
    }
    else if (cur_length == shortest_length) {//長度同等 
      shortest_num++;	//更新最短路徑數目 
      if (cur_men > max_men) {	//救援人數更多，則更新 
        max_men = cur_men;
      }
    }
    return;
  }
  
  /*從cur出發，通路所有可能路徑*/
  v[cur] = 1;//cur已經通路過
  for (int i = 0; i < n; i++) {
    if (v[i] == 1 || edge[cur][i] == 0)continue;
    DFS(i, cur_length + edge[cur][i], cur_men + men[i]);
  }
  
  /*從其他結點出發，能夠通路cur*/
  v[cur] = 0;
}



int main() {
  
  scanf("%d %d %d %d", &n, &e, &s, &d);
  
  /* 每個城市的可調用的救援人員數*/
  for (int i = 0; i < n; i++) {
    scanf("%d", &men[i]);
  }
  
  /* 每個城市之間的路徑長度*/
  for (int i = 0; i < e; i++) {
    int in1, in2, in3;
    scanf("%d %d %d", &in1, &in2, &in3);
    edge[in1][in2] = edge[in2][in1] = in3;
  }
  
  /*周遊各種從起點到終點的路徑*/
  DFS(s, 0, men[s]);	//s起點是目前路徑的終點，0是目前路徑的長度，men[s]是路徑的救援人員數 
  
  /*輸出最短路徑的數目，最短路徑上救援人數的最大值*/
  printf("%d %d\n", shortest_num, max_men);
  
  return 0;
}
           

代碼-python版