题解 | #最短路径问题#

import java.util.*;
import java.io.*;



public class Main {

    int[] he, ne, e, w, p;
    int idx;
    public static StreamTokenizer in = new StreamTokenizer(new BufferedReader(
                new InputStreamReader(System.in)));

    public static int nextInt() throws IOException {
        in.nextToken();
        return (int)in.nval;
    }

    public Main() {
        he = new int[1001];
        Arrays.fill(he, -1);
        ne = new int[200003];
        e = new int[200003];
        w = new int[200003];
        p = new int[200003];
        idx = 0;
    }

    public void add(int a, int b, int d, int m) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx;
        w[idx] = d;
        p[idx] = m;
        idx++;
    }

    public int[] dijkstra(int s, int end) {
        int[][] dists = new int[1001][2];
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->a[1] - b[1]);
        for (int i = 1; i < 1001; i++) {
            dists[i][0] = 0x3f3f3f3f;
        }
        boolean[] st = new boolean[1001];
        dists[s][0] = 0;
        q.add(new int[] {s, dists[s][0]});
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cur_p = cur[0];
            if (st[cur_p]) continue;
            st[cur_p] = true;
            for (int i = he[cur_p]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dists[j][0] > dists[cur_p][0] + w[i]) {
                    dists[j][0] = dists[cur_p][0] + w[i];
                    dists[j][1] = dists[cur_p][1] + p[i];
                    q.add(new int[] {j, dists[j][0]});
                }else if(dists[j][0] == dists[cur_p][0] + w[i]){
                    dists[j][1] = Math.min(dists[cur_p][1] + p[i],dists[j][1]);
                }
            }
        }
        return dists[end];
    }


    public static void main(String[] args) throws IOException {
        Main g = new Main();
        int n = nextInt();
        int m = nextInt();
        for (int i = 0; i < m; i++) {
            int r1 = nextInt();
            int r2 = nextInt();
            int r3 = nextInt();
            int r4 = nextInt();
            g.add(r1, r2, r3, r4);
            g.add(r2, r1, r3, r4);
        }
        int[] ret = g.dijkstra(nextInt(), nextInt());
        System.out.print(ret[0] + " " + ret[1]);
    }
}