美团8月15日笔试

public class Solution {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int x = in.nextInt();
        int y = in.nextInt();
        int[] waitTime = new int[n + 1];
        int[][] dis1 = new int[n + 1][n + 1];
        int[][] dis2 = new int[n + 1][n + 1];

        for (int i = 0; i <= n; i++) {
            Arrays.fill(dis1[i], -1);
            Arrays.fill(dis2[i], -1);
        }

        for (int i = 0; i < m; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            int w1 = in.nextInt();
            int w2 = in.nextInt();
            dis2[u][v] = dis2[v][u] = w1;
            dis1[u][v] = dis1[v][u] = w2;
        }

        for (int i = 1; i <= n; i++)
            waitTime[i] = in.nextInt();

        waitTime[y] = 0;

        for (int i = 1; i <= n; i++)
            dis1[i][i] = dis2[i][i] = 0;

        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++) {
                    if (dis1[i][k] != -1 && dis1[k][j] != -1 && (dis1[i][k] + dis1[k][j] < dis1[i][j] || dis1[i][j] == -1))
                        dis1[i][j] = dis1[i][k] + dis1[k][j];
                    if (dis2[i][k] != -1 && dis2[k][j] != -1 && (dis2[i][k] + dis2[k][j] < dis2[i][j] || dis2[i][j] == -1))
                        dis2[i][j] = dis2[i][k] + dis2[k][j];
                }
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                ans = Math.min(ans, Math.max(dis1[x][i], waitTime[i]) + dis2[i][j] + dis1[j][y]);
        System.out.println(ans);
    }
}