请AC君不要删本讨论，谢谢 在一个宁静的上午，一片片碎片划过天空，当有人还在感叹今晚的碎片雨真好看时。就有人发现一只只用代码......（未完待续）

本来想问一下姓艾名哎的“入”迪杰斯特拉算法（AC君爆肝ING），结果…… 我看不懂了，各位大佬看吧QAQ 迪杰斯特拉算法：从原理到 C++ 实战，掌握单源最短路径求解 迪杰斯特拉（Dijkstra）算法是图论领域解决单源最短路径问题的经典贪心算法，由荷兰计算机科学家艾兹赫尔・迪杰斯特拉于 1956 年提出。该算法适用于带非负权边的有向 / 无向图，能高效求解从单个起点到所有其他顶点的最短路径，广泛应用于地图导航、网络路由规划、资源调度等场景。本文将从核心原理出发，结合 C++ 代码实现，全方位讲解迪杰斯特拉算法。 一、算法核心原理 迪杰斯特拉算法的核心是 “贪心策略 + 松弛操作”，通过逐步锁定起点到各顶点的最短路径，最终得到全局最优解。具体步骤如下：1. 初始化定义距离数组dist[]，dist[v]表示起点到顶点v的当前最短距离，初始时起点dist[start] = 0，其余顶点dist[v] = ∞（无穷大）。定义布尔数组visited[]，标记顶点是否已确定最短路径，初始时所有顶点visited[v] = false。使用优先队列（小根堆）存储待处理的顶点（以 “当前最短距离 - 顶点编号” 的形式），初始时将起点(0, start)入队。2. 贪心选择每次从优先队列中取出当前距离起点最近的顶点 u（小根堆顶元素），若u已确定最短路径（visited[u] = true），则跳过；否则标记u为已确定（visited[u] = true）。3. 松弛操作遍历顶点u的所有邻接顶点v，计算 “起点→u→v” 的路径长度（dist[u] + weight(u, v)）。若该长度小于dist[v]，则更新dist[v]为该值，并将(dist[v], v)入队（即使v已入队，重复入队不影响，后续处理时会跳过已确定的顶点）。4. 终止条件当优先队列为空时，所有顶点的最短路径均已确定，算法结束。 二、算法关键特性权值限制： 必须保证所有边的权重非负，否则松弛操作无法保证后续不会出现更短路径（负权边场景需使用贝尔曼 - 福特算法或 SPFA 算法）。时间复杂度：邻接矩阵存储图：(O(n^2))（n为顶点数），每次遍历所有未确定顶点。邻接表 + 优先队列（二叉堆）：(O((n+e)logn))（e为边数），每个顶点和边最多处理一次，堆操作耗时logn。适用场景：单源最短路径（单个起点，多终点），支持有向图和无向图（无向图可视为双向有向图）。 三、C++ 代码实现（邻接表 + 优先队列版） 1. 代码框架采用邻接表存储图（空间效率更高，适合稀疏图），优先队列使用 C++ STL 的priority_queue（默认大根堆，需自定义比较规则改为小根堆）。 2. 代码说明 数据结构： Edge结构体：存储邻接顶点和边的权重，用于构建邻接表。 PII（pair<int, int>）：优先队列的元素类型，第一个值为当前最短距离，第二个值为顶点编号。 邻接表adj[]：adj[u]存储顶点u的所有出边。 核心函数dijkstra()： 初始化距离数组和标记数组，将起点入队。 循环取出优先队列的堆顶元素，跳过已确定的顶点，遍历邻接边执行松弛操作。 松弛操作中，若更新了顶点v的最短距离，则将新的距离和顶点入队。 主函数： 读取输入（顶点数、边数、起点，以及各条边的信息）。 调用dijkstra()算法，输出起点到所有顶点的最短距离。 3. 测试用例 输入示例（有向图）： 顶点说明：顶点 1 为起点，边 1→2（权重 2）、1→3（权重 5）、2→3（权重 1）、2→4（权重 3）、3→4（权重 2）。 输出结果： 结果分析：起点 1 到顶点 2 的最短距离为 2（1→2）。起点 1 到顶点 3 的最短距离为 3（1→2→3）。起点 1 到顶点 4 的最短距离为 5（1→2→4 或 1→2→3→4）。 四、常见误区与注意事项负权边问题： 迪杰斯特拉算法无法处理负权边。例如，若存在边 3→2（权重 - 5），则算法会错误地认为顶点 3 的最短距离为 5，而实际 1→3→2 的距离为 0，导致结果偏差。优先队列重复元素：优先队列中可能存在同一顶点的多个距离记录，无需额外删除旧记录，只需在取出时判断visited[u]，跳过已确定的顶点即可（重复记录不影响最终结果，仅增加少量堆操作）。顶点编号范围：代码中顶点编号从 1 开始（符合常规输入习惯），若需从 0 开始，只需调整main函数中的输入和输出循环。无穷大取值：代码中使用INT_MAX（int类型的最大值）表示无穷大，需注意路径长度溢出问题（若边权较大，可改用long long类型存储距离）。 五、扩展优化斐波那契堆优化： 理论上可将时间复杂度降至(O(nlogn + e))，但斐波那契堆实现复杂，实际工程中极少使用。双向迪杰斯特拉：同时从起点和终点出发执行贪心策略，相遇时停止，可减少堆操作次数，适合求解两点间的最短路径。处理无向图：只需在添加边时，同时添加u→v和v→u两条边（代码中注释部分）。 总结 迪杰斯特拉算法是单源最短路径问题的核心解法，其贪心策略保证了在非负权边场景下的正确性和高效性。本文通过原理讲解、C++ 代码实现和测试用例，完整呈现了算法的应用过程。掌握该算法不仅能解决图论基础问题，也能为复杂场景（如带约束的路径规划）提供思路。在实际开发中，需根据图的稀疏程度选择邻接矩阵或邻接表存储，并注意避开负权边、重复入队等常见误区。

https://www.acgo.cn/team/1954136972457275392(

听说把麦小鼠挂在头上会出非洲之心 也不知道是不是真的，反正我先试试，至少不会试试就逝世 出了告诉你们 给你们张网图看看吧 好了散会

今天上课时候的题： 文字版： 在你窗外闪耀的星星 题目描述 飞逝的的时光不会模糊我对你的记忆。难以相信从我第一次见到你以来已经过去了 3 年。我仍然还生动地记得，3 年前，在美丽的集美中学，从我看到你微笑着走出教室，你将头向后仰，柔和的晚霞照耀着你玫瑰色的脸颊。我明白，我已经沉醉于你了。之后，经过几个月的观察和窥探，你的优雅与智慧，你对待生活的态度和你对未来的愿望深切地在我心中留下了印象。你是迷人的阳光女孩，我总是梦想着与你分享余生。唉，实际上你远远超过了我最疯狂的梦想。我不知道如何桥起我与你之间的鸿沟。所以我没有任何计划，仅仅只是等待，等待一个适当的机会到来。直到现在，毕业的到来，我意识到我是个傻瓜，我应该创造机会并且抓住它而不只是等待。 这些日子里，我和我的朋友、室友、同学一个接一个地分开。我仍无法相信，在挥手之后，这些熟悉的面孔很快就会从我们的生活中消失，仅仅留下回忆。我明天就将离开学校。你已经计划远走高飞，追求你的未来，实现你的梦想。如果没有命运，也许我们不会再次相遇。所以今晚，我正在你的宿舍楼下徘徊，希望能偶然遇见你。但矛盾的是，你的美貌一定会使我心跳加速，我笨拙的舌头也许无法吐出一个字。我不记得我曾多少次经过你的宿舍楼，每次都希望看到你出现在阳台上或是窗台上。我不记得这个想法曾多少次在我的脑海中涌出：打电话叫她一起吃晚饭或是聊聊天。但每次，考虑到你的优秀和我的平凡，胆怯的优势超越勇气驱使我静静地离开。 毕业，意味着中学生活的终结。这些光荣与浪漫的时代结束。你可爱的微笑是我原来努力学习的动力，这单相思的爱情会被密封，作为一个我心灵深处的记忆。毕业，也意味着新生活的开始，一个到达光明未来的足迹。我真希望你在国外天天开心，一切顺利。同时，我将努力从幼稚中走出来，变得更加成熟。我的理想将是在现实中追求我的爱与幸福，我永远不会放弃。 再见了，我的公主！ 如果有一天，在某个天涯海角，我们有机会相聚，即使是白发苍苍的男人和女人，在那个时候，我希望我们可以成为好朋友来自豪地分享这个记忆，重温年轻快乐的激情。如果这个机会永远没有到来，我希望我是天空中的星星，在你的窗外闪烁。远远地保佑着你，就像一个朋友，每天晚上陪伴在你左右，一同分享甜美的梦亦或是一同经历可怕的梦。现在问题来了：天空可以理解为一条数轴，在这条数轴上分布着许多颗星星，对于每颗星星都有它的位置 XiX_iXi 和自身的亮度 BiB_iBi 。一个位置可能有多颗星星。而窗户所能看到的范围是一个给出的参数 WWW，我们看到的星星也包括窗户边缘的星星。现在，要你求出调整窗户位置后能看到星星的亮度之和最大值。 提示 样例说明： 对于 10%10\%10% 的数据，W=0W=0W=0（没有边缘）； 对于 40%40\%40% 的数据，W≤1000W \leq 1000W≤1000； 对于 100%100\%100% 的数据，1≤N≤1051 \leq N \leq 10^51≤N≤105，0≤W≤1050 \leq W \leq 10^50≤W≤105 ，1≤Xi≤1051 \leq X_i \leq 10^51≤Xi ≤105 ，1≤Bi≤1001 \leq B_i \leq 1001≤Bi ≤100。 除 W=0W=0W=0 的情况外，WWW 均为 ≥3\geq 3≥3 的奇数。 输入格式 一行 NNN,WWW，分别代表星星的数量和窗户的宽度。 余下 NNN 行，输入 XiX_iXi 和 BiB_iBi ，代表星星的坐标和亮度。 输出格式 一个数字，代表能看到星星的最大亮度和。 样例组输入#1 样例组输出#1

在搞之前，请先安装Sympy,如果没有安装，请在cmd里用以下命令安装： 好，安装好以后就可以开始了 先导入相关的模块 接下来是符号部分 准备妥当以后来解方程 这里给大家搞一个测试 请输入方程：8x3+10x2+100x+8=0 x=-575/(144*(3511/1728 + √(156201)/48)^(1/3)) - 5/12 + (3511/1728 + √(156201)/48)^(1/3) 不过有一个小问题，就是如果输入恒等式的话会显示“没有实数解！”

版本：X1.0&X1.1 > 特别鸣谢：@我爱死机 协助开发、规划与提供框架 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 语法讲解 XPR 功能 用于输出整数、浮点数、字符、字符串与布尔类型的数据 格式 数据类型对照表 数据类型代码 数据类型 i 整数 f 浮点数 c 字符 s 字符串 b 布尔 示例 代码： 运行结果： WAIT 功能 等待指定时间，单位：秒 格式 注意，参数[秒数]大于等于0 示例 代码： 运行结果： 等待一秒 CLEAR 功能 清屏 格式 示例 代码： 运行结果： 清屏 ENDL 功能 换行 格式 示例 代码： 运行结果： 换行

我和“吴陈😊”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！https://www.acgo.cn/application/1981630197495148544

感觉自己无限的付出 没结果 也没回报，我想也没必要了，身边的朋友可惜从来没把我当朋友，倒不如和谁都一样关系不远不近........

如题，萌新求带o(╥﹏╥)o

我以后谁都不回关了

链接：https://www.acgo.cn/contest/detail/14909matchRoundId=14909&examId=74564&openLevel=2&teamCode=1951470069377384448 点击链接或者图片参加吧！球球啦！！！

各位入侵acgo的三角洲小朋友们你们的扶贫梦该醒了 以下全有的自觉删号或是金盆洗手谢谢： 1 爱用唐人鼠鼠，耄耋头像，且尤其钟爱"教主"等字眼 2 叫错干员名字（例：哈吉蜂，卫龙，路娜等） 3 叫错红名字（例：心肺复苏机，麦小圈等） 4 喜欢扶贫主播，并试图给团员扶贫（此条可有可无） 5 抄题解大王，时空双修都是拿ai刷的 百无忌吧，南无啊马特拉斯，破防骂我替我挡灾

我和“咚咚🐏”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！https://www.acgo.cn/application/1881240671421403136

11月卡在第三层 现在卡在第七层的奖牌数量这道题

卡特兰数一个通项式： H(n)=(4n−2)/(n+1)∗H(n−1)H(n)=(4n-2)/(n+1)*H(n-1)H(n)=(4n−2)/(n+1)∗H(n−1) 斯特林数： S(i,j)=j∗S(i−1,j)+S(i−1,j−1)S(i,j)=j*S(i-1,j)+S(i-1,j-1)S(i,j)=j∗S(i−1,j)+S(i−1,j−1)

我是：主播贝利亚本人

题目描述 期末考试共两科，语文和数学，已知班上所有同学的语文分和数学分，请帮助求出每个人的期末分。 提示 1≤n≤50，每科成绩不超过 100 分，且不低于 0 分的整数。 样例解释： 第一个学生的语文 100，数学 100，期末总分 200 分。 第二个学生的语文 88，数学 75，期末总分 163 分。 第三个学生的语文 91，数学 85，期末总分 176 分。 输入格式 共三行，第一行一个整数 n， 表示学生人数。 第二行是每个人的语文成绩，分别用空格间隔的 n 个学生成绩。 第三行是每个人的数学成绩，分别用空格间隔的 n 个学生成绩。 输出格式 输出一行用空格间隔的 n 个学生的期末总分。 样例组输入#1 3 100 88 91 100 75 85 样例组输出#1 200 163 176 求题解！