LeetCode 3594. 所有人渡河所需的最短时间 — C 语言实现题目分析这道题是一个状态空间最短路问题。由于人可以来回摆渡状态存在循环无法用普通 DP必须用 Dijkstra 算法。状态定义 (people_mask, dir, stage)- people_mask二进制位为 1 表示该人还在起点营地- dir0 船在起点1 船在对岸- stage当前环境阶段索引0m-1C 语言实现要点C 没有内置优先队列需要手动实现 二叉堆Min-Heapc#include stdio.h#include stdlib.h#include math.h#include string.h#include float.htypedef struct {double cost;int people; // bitmask: 1 means still at start campint dir; // 0 boat at start, 1 boat at destinationint stage; // current stage index} State;// Min-Heap implementationtypedef struct {State *data;int size;int capacity;} MinHeap;MinHeap* createHeap(int capacity) {MinHeap *heap (MinHeap*)malloc(sizeof(MinHeap));heap-data (State*)malloc(sizeof(State) * capacity);heap-size 0;heap-capacity capacity;return heap;}void swap(State *a, State *b) {State tmp *a;*a *b;*b tmp;}void pushHeap(MinHeap *heap, State s) {if (heap-size heap-capacity) {heap-capacity * 2;heap-data (State*)realloc(heap-data, sizeof(State) * heap-capacity);}int i heap-size;heap-data[i] s;// sift upwhile (i 0) {int parent (i - 1) / 2;if (heap-data[parent].cost heap-data[i].cost) break;swap(heap-data[parent], heap-data[i]);i parent;}}State popHeap(MinHeap *heap) {State ret heap-data[0];heap-data[0] heap-data[--heap-size];// sift downint i 0;while (1) {int left 2 * i 1;int right 2 * i 2;int smallest i;if (left heap-size heap-data[left].cost heap-data[smallest].cost)smallest left;if (right heap-size heap-data[right].cost heap-data[smallest].cost)smallest right;if (smallest i) break;swap(heap-data[i], heap-data[smallest]);i smallest;}return ret;}int isEmpty(MinHeap *heap) {return heap-size 0;}void freeHeap(MinHeap *heap) {free(heap-data);free(heap);}// Precompute max_time for each subsetvoid precomputeMaxTime(int n, int *time, double *max_time) {int total 1 n;max_time[0] 0.0;for (int mask 1; mask total; mask) {int mx 0;for (int i 0; i n; i) {if (mask (1 i)) {if (time[i] mx) mx time[i];}}max_time[mask] (double)mx;}}// Precompute valid subsets (at most k people) for each settypedef struct {int **valid_subsets;int *count;int *capacity;} ValidSubsets;ValidSubsets* precomputeValidSubsets(int n, int k) {int total 1 n;ValidSubsets *vs (ValidSubsets*)malloc(sizeof(ValidSubsets));vs-valid_subsets (int**)malloc(sizeof(int*) * total);vs-count (int*)calloc(total, sizeof(int));vs-capacity (int*)malloc(sizeof(int) * total);for (int ppl 0; ppl total; ppl) {vs-capacity[ppl] 4;vs-valid_subsets[ppl] (int*)malloc(sizeof(int) * vs-capacity[ppl]);// Enumerate all subsets of pplint sub ppl;while (1) {int bits 0;int tmp sub;while (tmp) {bits tmp 1;tmp 1;}if (bits k) {if (vs-count[ppl] vs-capacity[ppl]) {vs-capacity[ppl] * 2;vs-valid_subsets[ppl] (int*)realloc(vs-valid_subsets[ppl],sizeof(int) * vs-capacity[ppl]);}vs-valid_subsets[ppl][vs-count[ppl]] sub;}if (sub 0) break;sub (sub - 1) ppl;}}return vs;}void freeValidSubsets(ValidSubsets *vs, int n) {int total 1 n;for (int i 0; i total; i) {free(vs-valid_subsets[i]);}free(vs-valid_subsets);free(vs-count);free(vs-capacity);free(vs);}double minTime(int n, int k, int m, int* time, int timeSize, double* mul, int mulSize) {int full_mask (1 n) - 1;int total_states 1 n;// Precompute max_time for each subsetdouble *max_time (double*)malloc(sizeof(double) * total_states);precomputeMaxTime(n, time, max_time);// Precompute valid subsetsValidSubsets *vs precomputeValidSubsets(n, k);// dist[people_mask][dir][stage]double ***dist (double***)malloc(sizeof(double**) * total_states);for (int i 0; i total_states; i) {dist[i] (double**)malloc(sizeof(double*) * 2);for (int j 0; j 2; j) {dist[i][j] (double*)malloc(sizeof(double) * m);for (int s 0; s m; s) {dist[i][j][s] DBL_MAX;}}}MinHeap *heap createHeap(1024);dist[full_mask][0][0] 0.0;pushHeap(heap, (State){0.0, full_mask, 0, 0});double result -1.0;while (!isEmpty(heap)) {State cur popHeap(heap);int ppl cur.people;int dir cur.dir;int spd cur.stage;if (cur.cost dist[ppl][dir][spd] 1e-9) {continue;}if (dir 1 cur.people 0) {result cur.cost;break;}if (dir 0) {// Boat at start: send a group (at most k people) to destinationfor (int idx 0; idx vs-count[ppl]; idx) {int sub vs-valid_subsets[ppl][idx];if (sub 0) continue;double d max_time[sub] * mul[spd];double new_cost cur.cost d;int new_ppl cur.people ^ sub;int new_spd ((spd (int)floor(d)) % m m) % m;if (new_cost dist[new_ppl][1][new_spd] - 1e-9) {dist[new_ppl][1][new_spd] new_cost;pushHeap(heap, (State){new_cost, new_ppl, 1, new_spd});}}} else {// Boat at destination: send exactly 1 person backint arrived full_mask ^ cur.people;for (int i 0; i n; i) {int mask 1 i;if (arrived mask) {double d max_time[mask] * mul[spd];double new_cost cur.cost d;int new_ppl cur.people | mask;int new_spd ((spd (int)floor(d)) % m m) % m;if (new_cost dist[new_ppl][0][new_spd] - 1e-9) {dist[new_ppl][0][new_spd] new_cost;pushHeap(heap, (State){new_cost, new_ppl, 0, new_spd});}}}}}// CleanupfreeHeap(heap);freeValidSubsets(vs, n);free(max_time);for (int i 0; i total_states; i) {for (int j 0; j 2; j) {free(dist[i][j]);}free(dist[i]);}free(dist);return result;}核心设计组件 说明Min-Heap 手动实现二叉堆支持 push / pop / isEmpty动态扩容max_time[mask] 预处理每个子集的最大 time[i]避免重复计算valid_subsets 预处理每个剩余集合的所有合法子集人数 ≤ k用动态数组存储三维 dist 数组 dist[mask][dir][stage]初始化为 DBL_MAX浮点比较 用 1e-9 容差避免精度问题编译运行bashgcc -o leetcode_3594 leetcode_3594.c -lm./leetcode_3594下载文件: [leetcode_3594.c](sandbox:///mnt/agents/output/leetcode_3594.c)
