原创于2017.04.03：最短路1.多源的Floyd,邻接矩阵实现，复杂度O（n^3），n<400;2.单源Dijkstra，邻接矩阵实现，无负边，复杂度O（n^2），n<10000；3.单源Dijkstra，邻接表实现，堆优化，无负边，复杂度O（ElogE），点多边少；4.单源bellman_ford，边集实现，可验负环，复杂度O（nE），nm<10^8；5.单源SPFA，邻接表+队列实现，可验负环

BD202301·公园题解考虑将整个移动过程分为两个部分：小度和度度熊汇合之前小度和度度熊汇合之后第一部分可以直接用Dijkstra算法直接搞定，第二部分可以考虑反向思考，从N点出发做一次Dijkstra，最后枚举每个汇合点即可得到答案。时间复杂度\(\Theta(nlogn)\)代码如下：#include

数据结构专题.CF1192B动态修改边权,查询树直径.方法1:首先考虑常规的树上问题,即树剖一类方法不便于处理和合并直径这一类信息,于是考虑拍成序列做(树莫队就是这种想法).考虑任一条路径是由左右端点和LCA连成,因此考虑可以用于求LCA的欧拉序列,刚好可以用差分法把任意一条路

P4253SCOI2015小凸玩密室一道紫色的dp。思路首先读题：要保证任意时刻所有被点亮的灯泡必须连通在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡考虑设\(g[u][1]\)为\(u\)子树第一个被选中的是子树的根的代价，\(g[u][0]\)为\(u\)子树内第一个选中的点不

发现今天做不了一点题，遂来补以前的比赛。B.378QAQandMocha'sArray秒了。排序，取最小的数记为\(x\)，再取最小的无法被\(x\)整除的数记为\(y\)，如果仍然存在无法被\(y\)整除的数，则无解。C.ChamoandMocha'sArray容易想到一个结论：如果一个数比它左边或右边的数小，那么

CF1515GPhoenixandOdometers首先进行缩点，对于一个点，与它不在同一连通分量的点无法形成回路，所以对每个连通分量分别计算。假设一个点\(u\)，有两个长度为\(a\)和\(b\)的环，那么就相当于找两个非负整数\(x\)和\(y\)，使得\(ax+by=w\)，其中\(w\)为题中的路径长，根据裴蜀定理

描述一个无向连通图，每个点\(u\)有点权\(w_u\)，处在\(u\)点时可以花费\(w_u\)的时间去任何一个距离\(u\)最短路径边数不超过\(f_u\)的点。现在，从\(1\)号点出发，对于每个\(1\lek\len\)，求出\(1\)到\(k\)需要的最小时间。\(n\leq200000\)\(m\leqn+50\)解决

查看设备资源状态disdevicemanuinfo查看序列号displayclock查看时间displaycpu查看CPU使用率displaymemory查看内存使用情况displayfan查看风扇displaypower查看电源disdevice

题意在坐标轴上给定N个点，坐标依次为x1,x2,...,xn,你需要从原点前往xn并且实现往返，其中从第一个点到第N-1个点上有加油站，其中第i个加油站可以花费p[i]购买f[i]升汽油，汽油的上限为H升，每行驶一单位距离需要花费一升汽油。在全部过程中每个加油站最多使用一次，判断是否可以完成行程并

题2：公路【题目描述】小苞准备开着车沿着公路自驾。公路上一共有nnn个站点，编号为从11

代码恢复训练2024.6.11.链接(luogu)链接(atcoder)分层图板子。结束。代码：点击查看代码/*Tips:你数组开小了吗？你MLE了吗？你觉得是贪心，是不是该想想dp？一个小时没调出来，是不是该考虑换题？打cf不要用umap！！！记住，rating是身外之物。该冲正解时冲正解！Problem:算

题目动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C吃 A现有 N 个动物，以 1∼N 编号。每个动物都是 A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这 N 个动物所构成的食物链关系进行描述：第一种说法是

P9433[NAPC-#1]Stage5-Conveyors题意简述给定一个\(N\)个节点的树形结构，每条边有边权，树上有\(k\)个关键点。接下来有\(q\)次询问，每次询问给定\(x,y\)两点，请计算从\(x\)开始经过这\(k\)个关键点（可以重复经过）再到\(y\)的最短路程。解题思路我们可以发现，如果\(x\)与\(y\)都

\(\text{update2024/6/9:}\)文中提到了速度较快的\(\text{DFS-SPFA}\)，虽然速度较好，但是容易被卡，例如模板！大家好，我是Weekoder！今天要讲的是负环的一些习题与负环在题目中的应用。一共有\(3\)个例题，分别为：\(\color{#52C41A}\texttt{P2136}\)，\(\color{#9D3DCF}\texttt{P2868

最短路系列：Dijkstra算法大家好，我是Weekoder!最短路系列的第二期：Dijkstra他来啦！那么废话不多说，让我们直奔主题吧。Dijkstra算法的用处与floyd算法不同的，Dijkstra算法用于求解单源最短路径。顾名思义，单源最短路径就是起点唯一，终点有多个的最短路算法。Dijkstra的思想是

最短路系列：SPFA算法大家好，我是Weekoder！终于，我们的最短路算法SPFA闪亮登场了！虽然话是这么说，但是我还是建议大家先学习Dijkstra算法，再来学习SPFA。并且我们在这里学习的SPFA算法只能通过P3371，并不能通过标准版的P4779。SPFA的原型——Bellman-Ford在学习SPFA之前，我

#include<iostream>#include<queue>usingnamespacestd;constintinf=2147483647;constintMAXX=2e5+11;intn,m,s,cnt;intdis[MAXX];intto[MAXX],nxt[MAXX],val[MAXX],h[MAXX];boolvis[MAXX];structnode{intv,w;friendbool

五星压行大师\(lyh\)表示：这是难得能让他的代码长度打破百行大关的题目（182行）。首先，根据科技与狠活，本题可以黑白染色。源点联向白格，黑格连向汇点。发现每个格子都可以连向四个方向，所以可以建立四个点，代表水管连到了上下左右四个方向。设四元组\((x,y,z,p)\)表示水管初始状态

题面：给你一个$n$个点$m$条边的有向图，第$i$条边$a_i$，$b_i$，$c_i$，表示一条单向边从$a_i$到$b_i$，长度为$c_i$，可能会有重边和自环。问能否从第$i$号点出发然后回到该点形成一个环？可以则输出最短时间，否则输出$-1$。思路：不难发现本题考查的是最短路。观察题面，发现边数

[USACO08JAN]TelephoneLinesS题目描述FarmerJohnwantstosetupatelephonelineathisfarm.Unfortunately,thephonecompanyisuncooperative,soheneedstopayforsomeofthecablesrequiredtoconnecthisfarmtothephonesystem.ThereareN(1≤

题目链接:https://atcoder.jp/contests/abc176/tasks/abc176_d双端队列bfs模版题.众所周知,用队列实现bfs,队列中存的是当前的状态那么在当前这种题目中,下一步怎么走有两种决策,我们要把两种决策可能导致的状态更新全部都记录下来,因此我们可以用双端队列来实现bfs,把正常走的

闻道有先后，术业有专攻当用来判断负环的时候，SPFA还挺好用的intpre[N];voidprint_path(ints,intt){if(s==t){cout<<s;return;}print_path(s,pre[t]);cout<<""<<t;}inthead[N],cnt;structEdge{intfrom,to,nxt,c;}e[

abc355e思路WC2024T3中知道一个技巧：如果知道区间\([l,r]\)的和就连边\(l\tor+1\)，那么想推出\([L,R]\)的区间和就要求\(L\)和\(R+1\)联通。按题意把符合要求的边连上，设边权为\(1\)跑bfs，求出\(L\)到\(R+1\)的最短路并记录路径上的点，就可以得到要询问的区间。

树的直径可能不是唯一的，但树的中点是唯一的，我的意思是..U81904【模板】树的直径有以下两种办法求得树的直径：两遍DFS（或BFS）：可以记录点树形DP：允许有负边权首先是两遍DFS可求路径点击查看代码inthead[N],cnt;structEdge{intfrom,to,nxt;llval;

原题链接大概思路我们已知一组不等式的解可以通过建边然后求最短路/最长路来得出而这里要求\(D_n-D_1\)的最大值，所以我们要求最短路。补充为什么要求最短路？对于任何一组不等式，我们都可以写成\(a_i-b_i\leqc_i\)建边含义假设\(D_n-D_1\)有最大值，那么通过这组不等