AcWing 1475. 紧急情况(java版)
原题链接
中等
作者:
kkop
,
2022-02-22 16:57:23
,
所有人可见
,
阅读 211
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
public class Main {
private static final int INF = 0x3f3f3f3f;
private static int[][] w;
private static int[] g;
private static int n, m, c1, c2;
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String[] strings = bufferedReader.readLine().split("\\s+");
n = Integer.parseInt(strings[0]);
m = Integer.parseInt(strings[1]);
c1 = Integer.parseInt(strings[2]);
c2 = Integer.parseInt(strings[3]);
w = new int[n + 10][n + 10];
for (int i = 0; i < n; i++) {
Arrays.fill(w[i], INF);
}
g = new int[n + 10];
String[] strings1 = bufferedReader.readLine().split("\\s+");
for (int i = 0; i < n; i++) {
g[i] = Integer.parseInt(strings1[i]);
}
for (int i = 0; i < m; i++) {
String[] strings2 = bufferedReader.readLine().split("\\s+");
w[Integer.parseInt(strings2[1])][Integer.parseInt(strings2[0])] = w[Integer.parseInt(strings2[0])][Integer.parseInt(strings2[1])] = Integer.parseInt(strings2[2]);
}
// dijkstra
boolean[] st = new boolean[n + 10];
int[] dirs = new int[n + 10];
Arrays.fill(dirs, INF);
int[] num = Arrays.copyOf(g, g.length);
int[] s = new int[n + 10];
s[c1] = 1;
dirs[c1] = 0;
PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(((o1, o2) -> Integer.compare(o1[0], o2[0])));
priorityQueue.add(new int[]{0, c1});
while (!priorityQueue.isEmpty()) {
int[] x = priorityQueue.poll();
if (st[x[1]]) {
continue;
}
st[x[1]] = true;
for (int i = 0; i < n; i++) {
if (dirs[i] > dirs[x[1]] + w[x[1]][i]) {
dirs[i] = dirs[x[1]] + w[x[1]][i];
priorityQueue.add(new int[]{dirs[i], i});
num[i] = num[x[1]] + g[i];
s[i] = s[x[1]];
} else {
if (dirs[i] == dirs[x[1]] + w[x[1]][i]) {
num[i] = Math.max(num[i], g[i] + num[x[1]]);
s[i] += s[x[1]];
}
}
}
}
System.out.println(s[c2] + " " + num[c2]);
}
}