| 175 | } |
| 176 | |
| 177 | public static void dijkstra() { |
| 178 | for (int i = 1; i <= cntt; i++) { |
| 179 | dist[i] = INF; |
| 180 | } |
| 181 | dist[s] = 0; |
| 182 | heap.add(new int[] { s, 0 }); |
| 183 | while (!heap.isEmpty()) { |
| 184 | int[] cur = heap.poll(); |
| 185 | int u = cur[0]; |
| 186 | int d = cur[1]; |
| 187 | if (!vis[u]) { |
| 188 | vis[u] = true; |
| 189 | for (int e = head2[u]; e > 0; e = next2[e]) { |
| 190 | int v = to2[e]; |
| 191 | int w = weight2[e]; |
| 192 | if (!vis[v] && dist[v] > d + w) { |
| 193 | dist[v] = d + w; |
| 194 | heap.add(new int[] { v, dist[v] }); |
| 195 | } |
| 196 | } |
| 197 | } |
| 198 | } |
| 199 | } |
| 200 | |
| 201 | public static void main(String[] args) throws Exception { |
| 202 | FastReader in = new FastReader(System.in); |