状压+dijk |floyd

floyd

本质是三维dp

// 返回一个二维列表，其中 (i,j) 这一项表示从 i 到 j 的最短路长度
// 如果无法从 i 到 j，则最短路长度为 LLONG_MAX / 2
// 允许负数边权
// 如果计算完毕后，存在 i，使得从 i 到 i 的最短路长度小于 0，说明图中有负环
// 节点编号从 0 到 n-1
// 时间复杂度 O(n^3 + m)，其中 m 是 edges 的长度
vector<vector<long long>> shortestPathFloyd(int n, vector<vector<int>>& edges) {
const long long INF = LLONG_MAX / 2; // 防止加法溢出
vector f(n, vector<long long>(n, INF));
for (int i = 0; i < n; i++) {
f[i][i] = 0;
}

for (auto& e : edges) {
int x = e[0], y = e[1];
long long wt = e[2];
f[x][y] = min(f[x][y], wt); // 如果有重边，取边权最小值
f[y][x] = min(f[y][x], wt); // 无向图
}

for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
if (f[i][k] == INF) { // 针对稀疏图的优化
continue;
}
for (int j = 0; j < n; j++) {
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
}
}
return f;
}

lc3594

预处理-状压

建图-dijk的妙妙vis_min

二进制状态表示还没过河的人，预处理每个子集过河时间

pq模拟「一批人过河、一个人返回」的过程，按阶段倍率计算总耗时

求所有人过河的最短总时间

class Solution {
public:
double minTime(int n, int k, int m, vector<int>& time, vector<double>& mul)

{
int u = 1 << n;
// 计算每个 time 子集的最大值
vector<int> max_time(u);
for (int i = 0; i < n; i++) {
int t = time[i];
int high_bit = 1 << i;
for (int mask = 0; mask < high_bit; mask++) {
max_time[high_bit | mask] = max({max_time[high_bit | mask], max_time[mask], t});
}
}
// 把 max_time 中的大小大于 k 的集合改为 inf
for (uint32_t i = 0; i < u; i++) {
if (popcount(i) > k) {
max_time[i] = INT_MAX;
}
}

vector dis(m, vector<double>(u, DBL_MAX));
using T = tuple<double, int, int>;
priority_queue<T, vector<T>, greater<>> pq;

auto push = [&](double d, int stage, int mask) {
if (d < dis[stage][mask]) {
dis[stage][mask] = d;
pq.emplace(d, stage, mask);
}
};

push(0, 0, u - 1); // 起点

while (!pq.empty()) {
auto [d, stage, left] = pq.top();
pq.pop();
if (left == 0) { // 所有人都过河了
return d;
}
if (d > dis[stage][left]) {
continue;
}
// 枚举 sub 这群人坐一艘船
for (int sub = left; sub > 0; sub = (sub - 1) & left) {
if (max_time[sub] == INT_MAX) {
continue;
}
// sub 过河
double cost = max_time[sub] * mul[stage];
int cur_stage = (stage + int(cost)) % m; // 过河后的阶段
// 所有人都过河了
if (sub == left) {
push(d + cost, cur_stage, 0);
continue;
}
// 枚举回来的人（可以是之前过河的人）
for (int s = (u - 1) ^ left ^ sub, lb; s > 0; s ^= lb) {
lb = s & -s;
double return_time = max_time[lb] * mul[cur_stage];
push(d + cost + return_time, (cur_stage + int(return_time)) % m, left ^ sub ^ lb);
}
}
}
return -1;
}
};