行业知识
图论入门题题解
2026-11-18 15:18:34
来源:互联网转载
✨���迎来到脑子不好的小菜鸟的文章✨
创作不易,麻烦点点赞哦
所属专栏:刷题_脑子不好的小菜鸟的博客-CSDN博客
我的主页:脑子不好的小菜鸟
文章特点:关键点和步骤讲解放在
代码相应位置
拓扑排序 / 家谱树
https://vjudge.net/contest/613618#problem/A
//拓扑排序:找到入度为0的点,将其写入答案,再删去其箭头,再继续找入度为0的点,循环往复vectoredeg[101];int n, deg[101] = { 0 };//入度void init()//建图{ cin >> n; int i, val; for (i = 1; i > val && val != 0) { edeg[i].push_back(val); deg[val]++; } }}void toposort()//拓扑排序{ int i; queue que; for (i = 1; i > s; int i; //初始化ans for (i = 1; i u >> v >> w; add(u, v, w); } int pos = s;//初始化pos为s while (visit[pos] == 0) { int minn = INT_MAX;//注意更新 visit[pos] = 1;//标记 //更新儿子的最短路径 for (i = head[pos]; i != 0; i = edge[i].next) { if (visit[edge[i].to] == 0 && ans[edge[i].to] > ans[pos] + edge[i].wei) ans[edge[i].to] = ans[pos] + edge[i].wei; } //找最短路径 for (i = 1; i > m >> s; for (i = 1; i u >> v >> w; add(u, v, w); } priority_queueque;//距离,点 que.push({0, s}); while (!que.empty()) { int qh = que.top().first; int h = que.top().second; que.pop();/*记得pop()!!!!!!!!!*/ if (visit[h] == 0) { visit[h] = 1; for (i = head[h]; i != 0; i = edge[i].next)//不断找下一个儿子,直到找完 { if (ans[edge[i].to] > ans[h] + edge[i].wei) { ans[edge[i].to] = ans[h] + edge[i].wei; if (visit[edge[i].to] == 0) que.push({ -ans[edge[i].to], edge[i].to }); } } } } for (i = 1; i n >> m; for (i = 1; i > v >> w; if (w
上一篇:独享服务器怎么托管