青烟绕指柔

最短路

2-SAT(1) bfs(6) Codeforces(3) dfs(4) Hash(1) HDU(2) KM(1) LCA(2) Link_Cut_Tree(1) LIS(1) Splay(1) STL(7) WQS二分(1) 中等难度(6) 主席树(4) 二分(1) 分块(1) 前缀和(1) 动态规划(15) 博弈论(1) 双连通分量(1) 图论(158) 堆(3) 字符串(5) 差分(1) 并查集(13) 拓扑排序(4) 数位dp(3) 数学(1) 数论(12) 无旋treap(2) 最小环(2) 最小生成树(11) 树形dp(1) 树状数组(16) 树结构(4) 树链剖分(1) 概率dp(2) 相对大小问题(1) 矩阵乘法(3) 离线算法(12) 线性基(2) 线段树(28) 背包问题(2) 莫队(1) 计算几何(8) 贪心(2) 距离表示(1) 题解(4)

/ 注册

全部文章 / 最短路（共18篇）

51Nod 1444破坏道路

题目：在某一个国家，那儿有n个城市，他们通过m条双向道路相连。城市从1到n编号。如果城市a和b通过一条道路直接相连，那么他们之间的距离就是一个小时。这个国家的道路网络可以允许你从任意一个城市到达另外的城市。现在你要破坏尽可能多的道路，但是要保证从城市s1到t1不超过l1小时，并且从城市s2到...

2019-12-27

0 711

跳楼机

题目描述 Srwudi的家是一幢h层的摩天大楼。由于前来学习的蒟蒻越来越多，srwudi改造了一个跳楼机，使得访客可以更方便的上楼。经过改造，srwudi的跳楼机可以采用以下四种方式移动：向上移动x层；向上移动y层；向上移动z层；回到第一层。一个月黑风高的大中午，DJL来到了...

2019-12-27

0 348

Codeforces 786B Legacy 线段树优化建图

题意翻译 Rick 和他的同事们做出了一种新的带放射性的婴儿食品(???根据图片和原文的确如此…)，与此同时很多坏人正追赶着他们。因此 Rick 想在坏人们捉到他之前把他的遗产留给 Morty。在宇宙中一共有 nn 个星球标号为 1 \sim n1∼n。Rick 现在身处于标号为 ss 的星球(...

2019-12-27

0 414

[USACO13OPEN]照片Photo

题目描述 Farmer John has decided to assemble a panoramic photo of a lineup of his N cows (1 <= N <= 200,000), which, as always, are conveniently num...

2019-12-27

0 406

[BJWC2012]冻结

题目描述 “我要成为魔法少女！” “那么，以灵魂为代价，你希望得到什么？” “我要将有关魔法和奇迹的一切，封印于卡片之中„„” 在这个愿望被实现以后的世界里，人们享受着魔法卡片（SpellCard，又名符卡）带来的便捷。现在，不需要立下契约也可以使用魔法了！你还不来试一试？比如，我们在魔法百...

2019-12-27

0 802

ICPC Russia Just the Last Digit

J. Just the Last Digit time limit per test2 seconds memory limit per test512 megabytes inputstandard input outputstandard output Jessie has recently s...

2019-12-27

0 473

2019ICPC银川 - Delivery Route

题目链接：Delivery Route 就是有负权的最短路，但是卡了spfa，由于x条路是双向的且为正，故我们可以缩点之后对块内跑Dijkstra，然后拓扑排序合并答案。但是我们对spfa优化一下就可以了（卡常专家）。我们都知道spfa有一个优化是SLF，就是用双端队列。这道题我们再加...

2019-12-27

0 554

Antinomy与伊尔美格

题目链接：Antinomy与伊尔美格比较明显的缩点，但是缩点之后怎么求最大值呢？我们缩点变成DAG之后，因为求最大值，而且不能往回走，所以跑最长路即可。 AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#...

2019-12-27

0 492