PAT 甲级考试【1003 Emergency】

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m;
    static int source, target;

    static int[] number;
    static int[][] matrix = new int[500][500];

    static int[] distance;

    static int shorts;

    static int maxpeople = 0;

    static boolean[] traved;

    static List<Integer>[] adj;

    static int ways = 0;

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] words = br.readLine().split("\\s+");
        n = Integer.valueOf(words[0]);
        m = Integer.valueOf(words[1]);
        source = Integer.valueOf(words[2]);
        target = Integer.valueOf(words[3]);

        number = new int[n];
        words = br.readLine().split("\\s+");
        for (int i = 0; i < n; i++) {
            number[i] = Integer.valueOf(words[i]);
        }
        adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            int c1, c2, l;
            words = br.readLine().split("\\s+");
            c1 = Integer.valueOf(words[0]);
            c2 = Integer.valueOf(words[1]);
            l = Integer.valueOf(words[2]);

            matrix[c1][c2] = l;
            matrix[c2][c1] = l;

            adj[c1].add(c2);
            adj[c2].add(c1);
        }
        //bfs;


        distance = new int[n];
        Arrays.fill(distance, Integer.MAX_VALUE / 2);
        distance[source] = 0;

        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return distance[o1] - distance[o2];
            }
        });

        queue.add(source);
        boolean[] visited = new boolean[n];

        while (!queue.isEmpty()) {
            int city = queue.poll();

            if( visited[city]) continue;

            if (distance[city] >= Integer.MAX_VALUE / 2) {
                break;
            }

            visited[city] = true;

            for (int adjcity : adj[city]) {
                if (distance[adjcity] > distance[city] + matrix[city][adjcity]) {
                    distance[adjcity] = distance[city] + matrix[city][adjcity];
                    queue.add(adjcity);
                }
            }
        }

        shorts = distance[target];
        //深度搜索
        traved = new boolean[n];
        traved[source] = true;
        travel(source, 0, number[source], 0);
        System.out.println(allpath.size() + " " + maxpeople);
    }

    static Set<List<Integer>> allpath = new HashSet<>();
    static List<Integer> path = new ArrayList<>();

    static public void travel(int city, int d, int people, int depth) {
        if (city == target && d == shorts) {
            List<Integer> sortedpath = new ArrayList<>();
            for (int x : path) {
                sortedpath.add(x);
            }
            Collections.sort(sortedpath);
            if (!allpath.contains(sortedpath)) {
                ways++;
                allpath.add(sortedpath);
            }

            if (people > maxpeople) {
                maxpeople = people;
            }
            return;
        }

        if (d > shorts) {
            return;
        }

        for (int u : adj[city]) {
            if (!traved[u]) {
                traved[u] = true;
                path.add(u);
                travel(u, d + matrix[city][u], people + number[u], depth + 1);
                traved[u] = false;
                int x = path.remove(depth);
            }
        }

    }
}