| 118 | } |
| 119 | |
| 120 | public static int dijkstra(int start, int target) { |
| 121 | for (int i = 1; i <= cntt; i++) { |
| 122 | for (int j = 0; j <= k; j++) { |
| 123 | dist[i][j] = INF; |
| 124 | vis[i][j] = false; |
| 125 | } |
| 126 | } |
| 127 | dist[start][0] = 0; |
| 128 | heap.add(new int[] { start, 0, 0 }); |
| 129 | while (!heap.isEmpty()) { |
| 130 | int[] cur = heap.poll(); |
| 131 | int node = cur[0]; |
| 132 | int time = cur[1]; |
| 133 | int cost = cur[2]; |
| 134 | if (!vis[node][time]) { |
| 135 | vis[node][time] = true; |
| 136 | if (node == target) { |
| 137 | return cost; |
| 138 | } |
| 139 | for (int e = head[node]; e > 0; e = nxt[e]) { |
| 140 | int v = to[e]; |
| 141 | int w = weight[e]; |
| 142 | if (!vis[v][time] && dist[v][time] > cost + w) { |
| 143 | dist[v][time] = cost + w; |
| 144 | heap.add(new int[] { v, time, dist[v][time] }); |
| 145 | } |
| 146 | if (time < k && !vis[v][time + 1] && dist[v][time + 1] > cost) { |
| 147 | dist[v][time + 1] = cost; |
| 148 | heap.add(new int[] { v, time + 1, dist[v][time + 1] }); |
| 149 | } |
| 150 | } |
| 151 | } |
| 152 | } |
| 153 | return -1; |
| 154 | } |
| 155 | |
| 156 | public static void clear() { |
| 157 | for (int i = 1; i <= cntt; i++) { |