数学（九） (5-5)

for (int s = 1; s＜(1＜＜k - 1); s++)

{

for (int t = (s - 1) & s; t＞0; t = (t - 1) & s)

{

for (int i = 0; i＜n; i++)

{

dp[s][i] = std::min(dp[s][i], dp[t][i] + dp[s ^ t][i]);

}

}

// dij

std::priority_queue＜std::pair＜ll, int＞＞ q;

std::vector＜bool＞ vis(n);

for (int i = 0; i＜n; i++)

{

if (dp[s][i] != inf)

q.push({-dp[s][i], i});

}

while (!q.empty())

{

auto [_, x] = ();

q.pop();

if (vis[x])

continue;

vis[x] = 1;

for (auto [y, w] : g[x])

{

if (dp[s][x] + w＜dp[s][y])

{

dp[s][y] = dp[s][x] + w;

q.push({-dp[s][y], y});

}

}

}

}

for (int i = k - 1; i＜n; i++)

{

std::cout＜＜dp[(1 << k - 1) - 1][i]＜＜"\n";

}

return 0;

}

本文使用 Zhihu On VSCode 创作并发布

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。