AcWing 1128. 信使
原题链接
简单
作者:
kkop
,
2022-02-25 11:13:23
,
所有人可见
,
阅读 141
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main {
private static int[] h, e, ne, w;
private static int n, m, idx;
private static int INF = 0x3f3f3f3f;
public static void main(String[] args) throws IOException {
BufferedReader inReader = new BufferedReader(new InputStreamReader(System.in));
String[] strings = inReader.readLine().trim().split("\\s+");
n = Integer.parseInt(strings[0]);
m = Integer.parseInt(strings[1]);
h = new int[n + 10];
e = new int[2*m + 10];
ne = new int[2*m + 10];
w = new int[2*m + 10];
Arrays.fill(h, -1);
for (int i = 0; i < m; i++) {
String[] s = inReader.readLine().trim().split("\\s+");
int a = Integer.parseInt(s[0]), b = Integer.parseInt(s[1]), c = Integer.parseInt(s[2]);
add(a, b, c); add(b, a, c);
}
System.out.println(dijkstra());
}
private static int dijkstra() {
int[] dirs = new int[n + 10];
Arrays.fill(dirs, INF);
boolean[] st = new boolean[n + 10];
PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(o->o[0]));
priorityQueue.offer(new int[] {0, 1});
dirs[1] = 0;
while (!priorityQueue.isEmpty()) {
int[] a = priorityQueue.poll();
if (st[a[1]]) continue;
st[a[1]] = true;
for (int i = h[a[1]]; i != -1; i = ne[i]) {
int j = e[i];
if (dirs[j] > dirs[a[1]] + w[i]) {
dirs[j] = dirs[a[1]] + w[i];
priorityQueue.offer(new int[] {dirs[j], j});
}
}
}
int res = -1;
for (int i = 1; i <= n; i++) {
res = Math.max(res, dirs[i]);
}
return res == INF ? -1 : res;
}
private static void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
}