解法一：Dijkstra最短路径

相比经典的最短路问题，多了一个求解方案数的步骤，在进行松弛操作时，如果遇到路径更短的方案，就用其方案数更新，如果路径长度相等，则加上其方案数。
注意本题是无向图。拿堆优化写的一直WA，没找到原因，心累😪

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
class Main {
    public static void main(String[] args) throws IOException {
        // StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        String[] input = in.readLine().split(" ");
        final int N = Integer.parseInt(input[0]);
        final int M = Integer.parseInt(input[1]);
        final int src = Integer.parseInt(input[2]);
        final int dst = Integer.parseInt(input[3]);
        // 方案数
        int[] solutions = new int[N];
        Point[] points = new Point[N];
        for (int i = 0; i < N; ++i) {
            points[i] = new Point();
        }
        input = in.readLine().split(" ");
        // 每个城市的救援队员人数
        int[] values = new int[N];
        for (int i = 0; i < N; ++i) {
            values[i] = Integer.parseInt(input[i]);
        }
        // 邻接矩阵
        int[][] graph = new int[N][N];
        for (int i = 0; i < N; ++i) {
            Arrays.fill(graph[i], 0x3f3f3f3f);
        }
        for (int i = 0, u, v, dis; i < M; ++i) {
            input = in.readLine().split(" ");
            u = Integer.parseInt(input[0]);
            v = Integer.parseInt(input[1]);
            dis = Integer.parseInt(input[2]);
            graph[u][v] = dis;
            graph[v][u] = dis;
        }
        points[src].dis = 0;
        points[src].val = values[src];
        solutions[src] = 1;
        for (int i = 0; i < N; ++i) {
            int start = -1;
            for (int j = 0; j < N; ++j) {
                if ((!points[j].isVisited) && ((start == -1) || (points[start].dis > points[j].dis))) {
                    start = j;
                }
            }
            points[start].isVisited = true;
            for (int j = 0; j < N; ++j) {
                if (points[j].dis > points[start].dis + graph[start][j]) {
                    points[j].dis = points[start].dis + graph[start][j];
                    solutions[j] = solutions[start];
                    points[j].val = points[start].val + values[j];
                } else if (points[j].dis == points[start].dis + graph[start][j]) {
                    solutions[j] += solutions[start];
                    points[j].val = Math.max(points[j].val, values[j] + points[start].val);
                }
            }
        }
        System.out.println(solutions[dst] + " " + points[dst].val);
        // out.flush();
    }
}
class Point {
    // 到源点的最小距离
    int dis;
    // 到达该点的最大救援队员的人数
    int val;
    // 是否访问过
    boolean isVisited;
    Point() {
        dis = 0x3f3f3f3f;
        val = 0;
        isVisited = false;
    }
}