美团8月15日笔试
第四题一直45%，有没有老哥帮忙看下哪里有问题，感觉就是裸的floyd啊
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);
}
} 