数学（九） (5-4)

std::vector＜std::array

for (auto &[c, l, r] : quries)

{

std::cin＞＞l＞＞r＞＞c;

}

std::sort(quries.begin(), quries.end());

ll ans = 0;

DSU dsu(n);

for (auto [c, l, r] : quries)

{

ans += c;

int x = dsu.find(l);

while (x＜r)

{

rge(x, x + 1);

x = dsu.find(x);

ans += c;

}

}

if (dsu.find(1) != n)

{

ans = -1;

}

std::cout＜＜ans＜＜'\n';

return 0;

}

G - Last Major City

前有典题...

斯坦纳树，模板代码几乎原封不动放上去就能过，原理得仔细学习，代码倒是很简单

dp[S][i]表示以 i 为根，节点集合为 S 的最小路径长，有

dp[S][i]＝min(dp[S][i]，dp[T][i]＋dp[S ⨁ T][i])，T ⊆ S

然后再对 S 做一个最短路就可以了

int main()

{

std::ios::sync_with_stdio(false);

std::cin.tie(0);

int n, m, k;

std::cin＞＞n＞＞m＞＞k;

std::vector＜std::vector＜std::pair＜int, int＞＞＞ g(n);

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

{

int a, b, c;

std::cin＞＞a＞＞b＞＞c;

a--, b--;

g[a].push_back({b, c});

g[b].push_back({a, c});

}

const ll inf = 1e18;

std::vector dp(1＜＜(k - 1), std::vector＜ll＞(n + 1, inf));

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

{

dp[1＜＜i][i] = 0;

}

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