迪杰斯特拉算法学习笔记

迪杰斯特拉算法学习笔记

迪杰斯特拉算法学习笔记问题引入给定一个含有 $n$ 个点,$m$ 条边的有向图,每一条边有一个权值 $a(a \ge 0)$ ,定义一个点 $i$ 到一个点 $j$ 的路径的长度为从 $i$ 到 $j$ 所经过的边的权值之和。给定源点 $s$ ,求 $s$ 到其他点的最短路。问题分析假设我们当前在寻找 $s$ 到 $t$ 的最短路,并且这条最短路径是 $sv_1v_2\cdots v_kt$ 。那么我们一定是沿着最短路来走的。换句话说,任取 $i, j\in [0, k + 1]$,使得 $v_0$ 表示 $s$ ,$v_{k + 1}$ 表示 $t$,则 $s$ 到 $t$ 这条路径中...

ACM 科技 2020-04-27 AM 394℃ 1条
“Shopee杯” E 起来编程暨武汉大学 2020 年大学生程序设计大赛(网络预选赛)解题报告

“Shopee杯” E 起来编程暨武汉大学 2020 年大学生程序设计大赛(网络预选赛)解题报告

比赛地址:“Shopee杯” E 起来编程暨武汉大学 2020 年大学生程序设计大赛(网络预选赛)整场比赛体验不错,感觉难度略小于 div2 。无论一开始怎么翻车,最后 AK 了还是很开心的。A - A Monument For Heroes题目大意给定 $n$ 个由小写字母组成的字符串,选取其中的若干个,将它们排成一个新的串 $s$ ,要求如下:若选取的两个字符串在 $s$ 中是相邻的,那么前面的字符串的最后一个字母应当与后面的字符串的第一个字母相同。特别地,选取的最后一个字符串的最后一个字母应当与选取的第一个字符串的第一个字母相同。选取的字符串在 $s$ 中的顺序应该与输入的顺序相同...

校内训练赛解题报告,解题报告 2020-04-12 PM 329℃ 1条
午夜杂感

午夜杂感

想体验一下屏幕在深夜微微发亮的感觉,于是我关了灯。下了一天的雨,停了,剩下满世界的水汽。偶尔有雨滴打在窗台上,滴答作响,为我的胡思乱想伴奏。窗外除了黑夜,还是黑夜,没有颜色,也没有声音,键盘声虽然不是什么动听的交响乐,却莫名地让我心静。好想找一个人说说话啊,但我的手机也不再主动亮起,就像窗外一样,没有颜色,也没有声音。有人问我,何谓生,何谓死?如果我们终将化成岁月里的一粒尘埃,那么生又有何意义?但就从我的内心而言,我很不喜欢去仔细思考这些问题,因为这些思绪会让我的心静下来之后继续下沉,最终到达谷底。这样的状态与我内心所期望达到的状态是相悖的,我无数次在心中勾画出一个乌托邦,舒畅、平静、祥...

心情日记 2020-02-16 AM 260℃ 0条
武汉大学新生寒假集训测试 Day7 解题报告

武汉大学新生寒假集训测试 Day7 解题报告

比赛地址:武汉大学新生寒假集训测试 Day7本次比赛难度相对简单,可是我还是因为一些东西推错了导致没有 AK ,流下了菜的泪水……本次比赛全部题目均来源于 Codeforces 。A - Two-gram题目大意给定一个长度为 $n$ 的字符串 $s$ ,定义两位字符串为由两个字符组成的字符串。求该字符串的所有子串中,出现次数最多的两位字符串。$1\le n\le 100$ 。解题思路注意到所有的两位字符串都是由 $s$ 中相邻的两个字符组成的,所以暴力枚举所有的两位字符串,用 map 统计数量,找最大值即可。时间复杂度 $\Theta(n)$ 。#include <cstdio&...

校内训练赛解题报告,解题报告 2020-02-09 PM 534℃ 2条
武汉大学新生寒假集训测试 Day6 解题报告

武汉大学新生寒假集训测试 Day6 解题报告

比赛地址:武汉大学新生寒假集训测试 Day6第一场有两人 AK 的练习赛,似乎是另外一位大佬终于开始认真打了?我这场比赛的代码写得都很暴力,希望读者能有一定的心理准备。本次比赛所有题目均来自于 Codeforces 。A - Vasya and Multisets题目大意给定一个含有 $n$ 个数的多集 $s$ (可以含有相同元素的集合)。对于一个多集,定义一个数是“好数”当且仅当这个数在该多集中该数出现且仅出现了一次。现要将 $s$ 划分为两个多集(其中一个多集可以为空)$a$ 和 $b$ ,要求 $a$ 中“好数”的数量等于 $b$ 中“好数”的数量。给出任意一种分配方式或者无解。$...

校内训练赛解题报告,解题报告 2020-02-08 PM 259℃ 0条