PAT（甲）1003. Emergency（25）

原题连接：

1003. Emergency

我的思路:

1. 利用 DFS（深度优先搜索）从起点开始找路（同时记录路径长度和经过的各个节点）
2. 每找到一条可达路径，先判定这条路径的长度
3. 如果大于当前最短路则直接跳过
4. 如果等于当前最短路，则查看该路上可以集结几只队伍，如果队伍数大于当前最多队伍数，则更新，否则跳过
5. 如果小于当前最短路，则更新当前最短路，并更新当前最多队伍

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static List<Integer> path = new ArrayList<>();
    private static int minLength = 0, maxTeams = 0, thisLength = 0, viablePath = 0;
    private static int[] teams;
    private static boolean[] marked;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int[][] cityMap;  //我使用邻接矩阵法表示图

        int n = in.nextInt();
        int m = in.nextInt();
        int from = in.nextInt();
        int to = in.nextInt();

        teams = new int[n];
        marked = new boolean[n];
        cityMap = new int[n][n];

        for (int i = 0; i < n; i++){
            teams[i] = in.nextInt();
        }

        /*
         注意：在构造图时, 因为我使用邻接矩阵法表示图, 而且图本身为无向图
              所以在构造时 start->end 和 end->start 都要赋值
         */
        for (int i = 0; i < m; i++){
            int start, end, len;
            start = in.nextInt();
            end = in.nextInt();
            len = in.nextInt();
            cityMap[start][end] = len;
            cityMap[end][start] = len;
        }

        dfs(cityMap, from, to);
        System.out.println(viablePath + " " + (maxTeams + teams[from]));
    }

    private static void dfs(int[][] map, int from, int to){
        if (from == to) {
            if (minLength <= 0 || thisLength <= minLength){
                if (thisLength == minLength){
                    viablePath++;
                }else {
                    minLength = thisLength;
                    viablePath = 1;
                    maxTeams = 0;
                }
                int thisTeams = 0;
                for (int i = 0; i < path.size(); i++){
                    thisTeams += teams[path.get(i)];
                }
                if (thisTeams > maxTeams){
                    maxTeams = thisTeams;
                }
            }
            return;
        }

        /*
         使用 dfs 找路
         注意：因为我们不是遍历图, 而是寻找所有的路径
              所以要在回溯时及时恢复各个变量的原值
         */
        marked[from] = true;
        for (int i = 0; i < map.length; i++){
            if (map[from][i] > 0 && !marked[i]){
                path.add(i);
                thisLength += map[from][i];
                dfs(map, i, to);
                thisLength -= map[from][i];
                path.remove(path.size() - 1);
            }
        }
        marked[from] = false;
    }
}