标签 最短路 下的文章:

2725: [Violet 6]故乡的梦 线段树 + 最短路
发表于: | 分类:Oi | 评论:0 | 阅读:122
显然一次修改如果不在最短路上那就一点影响都没有 如果在最短路上那么采取绕道即可,在跑最短路的时候维护出 $f(x)$ 表示从 $s$ 到 $x$ 的路径上第一个不在 $s,t$ 最短路径的点,右面同理维护 $g(x)$ 然后我们就可以通过 $f(x)+val_{(...

阅读全文>>

4456: [Zjoi2016]旅行者 最短路 分治 卡常数
发表于: | 分类:Oi | 评论:0 | 阅读:142
这是一道非常不错的题目……我们可以利用分治+最短路来解决这个问题 具体的方法是每次定位出一个矩形表示处理这个矩形的询问,然后每次把这个矩形分成相等的两部分,分的依据是每次把长的边劈成两半,然后考虑枚举这条线上的每一个点跑最短路,然后更新一下所有询问,显然这时两个点...

阅读全文>>

BZOJ 1097 [POI2007]旅游景点$atr$
发表于: | 分类:Oi | 评论:0 | 阅读:205
给出一张n个点m条边的无向连通图,现在一个人从1号点出发,想要遍历2~k+1号节点(不一定要按照顺序)然后到n号节点去,但是D个旅行顺序的要求,顺序要求的格式为D1,D2,代表在到达D2之前必须到达D1.问最短的旅行距离。 k太小了,一下子就有想法 直接全排列好像...

阅读全文>>

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP