| 72 | } |
| 73 | |
| 74 | public static void dijkstra() { |
| 75 | for (int i = 1; i <= m; i++) { |
| 76 | addEdgeG(edge[i][0], edge[i][1], edge[i][2]); |
| 77 | addEdgeG(edge[i][1], edge[i][0], edge[i][2]); |
| 78 | } |
| 79 | Arrays.fill(dist, 1, n + 1, INF); |
| 80 | Arrays.fill(visit, 1, n + 1, false); |
| 81 | dist[1] = 0; |
| 82 | heap.add(new int[] { 1, 0 }); |
| 83 | int[] cur; |
| 84 | int x, v; |
| 85 | while (!heap.isEmpty()) { |
| 86 | cur = heap.poll(); |
| 87 | x = cur[0]; |
| 88 | v = cur[1]; |
| 89 | if (!visit[x]) { |
| 90 | visit[x] = true; |
| 91 | for (int e = headg[x], y, w; e > 0; e = nextg[e]) { |
| 92 | y = tog[e]; |
| 93 | w = weightg[e]; |
| 94 | if (!visit[y] && dist[y] > v + w) { |
| 95 | dist[y] = v + w; |
| 96 | heap.add(new int[] { y, dist[y] }); |
| 97 | } |
| 98 | } |
| 99 | } |
| 100 | } |
| 101 | } |
| 102 | |
| 103 | public static void addEdgeK(int u, int v) { |
| 104 | nextk[++cntk] = headk[u]; |