| 70 | |
| 71 | // 来自讲解064，dijkstra算法 |
| 72 | public static void dijkstra() { |
| 73 | heap.add(new long[] { 0, 0 }); |
| 74 | distance[0] = 0; |
| 75 | long[] cur; |
| 76 | int u; |
| 77 | long w; |
| 78 | while (!heap.isEmpty()) { |
| 79 | cur = heap.poll(); |
| 80 | u = (int) cur[0]; |
| 81 | w = cur[1]; |
| 82 | if (visited[u]) { |
| 83 | continue; |
| 84 | } |
| 85 | visited[u] = true; |
| 86 | for (int ei = head[u], v; ei > 0; ei = next[ei]) { |
| 87 | v = to[ei]; |
| 88 | if (!visited[v] && distance[v] > w + weight[ei]) { |
| 89 | distance[v] = w + weight[ei]; |
| 90 | heap.add(new long[] { v, distance[v] }); |
| 91 | } |
| 92 | } |
| 93 | } |
| 94 | } |
| 95 | |
| 96 | public static long compute() { |
| 97 | dijkstra(); |