根据搜索结果这是 LeetCode 3594 所有人渡河所需的最短时间 的 Java 实现。题目理解- n 个人在营地船一次最多载 k 人- 环境有 m 个周期性阶段每个阶段有速度倍率 mul[j]- 过河时间 组内最大 time[i] × mul[j]- 过河后阶段前进 floor(d) % m 步- 若还有人没过河需 1 人划船返回返回时间 time[r] × mul[current]- 求所有人过河的最短总时间无法完成返回 -1核心思路由于 n 12用 状态压缩 Dijkstra- 状态(ppl, dir, spd) — 剩余在营地的人(bitmask)、船的位置(0营地/1对岸)、当前阶段- 船在营地枚举不超过 k 人的子集过河- 船在对岸枚举 1 人划船返回- 用 Dijkstra 求最短路时间只增不减Java 实现javaimport java.util.*;class Solution {public double minTime(int n, int k, int m, int[] time, double[] mul) {int FULL (1 n) - 1;// 预处理每个子集的最大 timedouble[] maskTime new double[1 n];for (int mask 1; mask (1 n); mask) {for (int i 0; i n; i) {if ((mask (1 i)) ! 0) {maskTime[mask] Math.max(maskTime[mask], time[i]);}}}// 预处理每个状态下可行的过河子集ListInteger[] g new List[1 n];for (int ppl 0; ppl (1 n); ppl) {g[ppl] new ArrayList();for (int sub 1; sub (1 n); sub) {if (Integer.bitCount(sub) k (sub | ppl) ppl) {g[ppl].add(sub);}}}// dist[ppl][dir][spd] 最小时间double INF Double.MAX_VALUE / 2;double[][][] dist new double[1 n][2][m];for (int i 0; i (1 n); i) {for (int j 0; j 2; j) {Arrays.fill(dist[i][j], INF);}}// Dijkstra: [cost, ppl, dir, spd]PriorityQueuedouble[] pq new PriorityQueue((a, b) - Double.compare(a[0], b[0]));// 辅助函数尝试更新状态autoPush (double cost, int ppl, int dir, int spd) - {if (cost dist[ppl][dir][spd]) {dist[ppl][dir][spd] cost;pq.offer(new double[]{cost, ppl, dir, spd});}};dist[FULL][0][0] 0;pq.offer(new double[]{0, FULL, 0, 0});while (!pq.isEmpty()) {double[] cur pq.poll();double cost cur[0];int ppl (int) cur[1];int dir (int) cur[2];int spd (int) cur[3];if (cost dist[ppl][dir][spd] 1e-9) continue;if (dir 0) { // 船在营地过河for (int mask : g[ppl]) {double d maskTime[mask] * mul[spd];double newCost cost d;int newPpl ppl ^ mask;int newSpd (spd (int) Math.floor(d)) % m;if (newCost dist[newPpl][1][newSpd] - 1e-9) {dist[newPpl][1][newSpd] newCost;pq.offer(new double[]{newCost, newPpl, 1, newSpd});}}} else { // 船在对岸返回if (ppl 0) { // 全部到达return cost;}for (int i 0; i n; i) {int mask 1 i;if ((mask ppl) 0) { // 人在对岸double d maskTime[mask] * mul[spd];double newCost cost d;int newPpl ppl ^ mask;int newSpd (spd (int) Math.floor(d)) % m;if (newCost dist[newPpl][0][newSpd] - 1e-9) {dist[newPpl][0][newSpd] newCost;pq.offer(new double[]{newCost, newPpl, 0, newSpd});}}}}}return -1;}}优化版本避免 lambda纯 Javajavaimport java.util.*;class Solution {public double minTime(int n, int k, int m, int[] time, double[] mul) {int FULL (1 n) - 1;// 预处理每个子集的最大 timedouble[] maskTime new double[1 n];for (int mask 1; mask (1 n); mask) {for (int i 0; i n; i) {if ((mask (1 i)) ! 0) {maskTime[mask] Math.max(maskTime[mask], time[i]);}}}// 预处理每个状态下可行的过河子集不超过k人且都是剩余人口ListInteger[] g new List[1 n];for (int ppl 0; ppl (1 n); ppl) {g[ppl] new ArrayList();for (int sub 1; sub (1 n); sub) {if (Integer.bitCount(sub) k (sub | ppl) ppl) {g[ppl].add(sub);}}}double INF 1e18;double[][][] dist new double[1 n][2][m];for (int i 0; i (1 n); i) {for (int j 0; j 2; j) {Arrays.fill(dist[i][j], INF);}}// Dijkstra: [cost, ppl, dir, spd]PriorityQueuedouble[] pq new PriorityQueue((a, b) - {return Double.compare(a[0], b[0]);});dist[FULL][0][0] 0;pq.offer(new double[]{0, FULL, 0, 0});while (!pq.isEmpty()) {double[] cur pq.poll();double cost cur[0];int ppl (int) cur[1];int dir (int) cur[2];int spd (int) cur[3];if (cost dist[ppl][dir][spd] 1e-9) continue;if (dir 0) { // 船在营地过河到对岸for (int mask : g[ppl]) {double d maskTime[mask] * mul[spd];double newCost cost d;int newPpl ppl ^ mask;int newSpd (spd (int) Math.floor(d)) % m;if (newCost dist[newPpl][1][newSpd] - 1e-9) {dist[newPpl][1][newSpd] newCost;pq.offer(new double[]{newCost, newPpl, 1, newSpd});}}} else { // 船在对岸1人返回if (ppl 0) { // 全部到达return cost;}for (int i 0; i n; i) {int mask 1 i;if ((mask ppl) 0) { // 第i人在对岸double d maskTime[mask] * mul[spd];double newCost cost d;int newPpl ppl | mask; // 把人加回营地int newSpd (spd (int) Math.floor(d)) % m;if (newCost dist[newPpl][0][newSpd] - 1e-9) {dist[newPpl][0][newSpd] newCost;pq.offer(new double[]{newCost, newPpl, 0, newSpd});}}}}}return -1;}}复杂度分析指标 复杂度 说明时间 O(2ⁿ × m × (C(n,≤k) n) × log(2ⁿ × m)) Dijkstra 状态数 × 转移数 × log空间 O(2ⁿ × m) dist 数组 优先队列关键点1. 状态设计(ppl, dir, spd) 三元组其中 ppl 是 bitmask 表示营地剩余的人2. 阶段循环newSpd (spd floor(d)) % m环境周期性变化3. Dijkstra时间只增不减标准最短路4. 预处理子集最大时间和可行子集列表避免重复计算5. 浮点精度比较时用 1e-9 容差