数据是不是有点问题啊
我邻接表开n+1, 可以过45%, 然后爆索引越界, 开200001能AC
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { int n = I(); int m = I(); List<int[]>[] g = new ArrayList[200001]; // List<int[]>[] g = new ArrayList[n+1]; // 这里用n+1,只能过45%, 下面的建图爆索引越界 Arrays.setAll(g, k -> new ArrayList<>()); for (int i = 0; i < m; i++) { int u = I(), v = I(), w = I(); g[u].add(new int[]{v, w}); // u,v应该是小于等于n的, 开n+1没有理由在这越界吧, 数据出错了? g[v].add(new int[]{u, w}); } //求1->n的最短路长度 long[] dist = new long[n + 1]; Arrays.fill(dist, Long.MAX_VALUE / 2); dist[1] = 0; boolean[] visited = new boolean[n + 1]; Queue<V> queue = new PriorityQueue<>(Comparator.comparingLong(a -> a.weight)); queue.add(new V(1, 0)); while (!queue.isEmpty()) { V cur = queue.poll(); if (visited[cur.v]) continue; visited[cur.v] = true; //更新邻居 for (int[] e : g[cur.v]) { int to = e[0], weight = e[1]; if (!visited[to] && dist[cur.v] + weight < dist[to]) {//从cur->to更短 dist[to] = dist[cur.v] + weight; queue.add(new V(to, dist[to])); } } } System.out.println(dist[n] == Long.MAX_VALUE / 2 ? "qwb baka" : dist[n]); } static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535); static StreamTokenizer st = new StreamTokenizer(bf); static int I() throws IOException { st.nextToken(); return (int) st.nval; } static class V { int v; long weight; public V(int v, long weight) { this.v = v; this.weight = weight; } } }