分类 最短路 下的文章

BZOJ 1295: [SCOI2009]最长距离

Solution可以直接求下任意两点的最短路,把障碍看做是权值为 1 的点,其他点权值为 0,这样最短路的意义就是两点间拆至少多少个障碍才能联通。之后枚举任意两个点更新答案就可以了Code#include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <cmath> using namespace std; const int N = 32; int n, m, t; int a[N][N]; char s[N]- 阅读剩余部分 -

BZOJ 1491: [NOI2007]社交网络

Solution直接按照题意模拟就可以了,最短路用 floyd 就可以啦,还可以顺便记录下路径数。Code#include <cstdio> #include <algorithm> #include <cstring> #define long long long using namespace std; const int N = 200; int n, m; int f[N][N]; long cnt[N][N]; int main() { memset(f, 0x3f, sizeof f); scanf("- 阅读剩余部分 -

BZOJ 4289: PA2012 Tax

Solution这题是考最短路建图,还是挺有趣的,但是我 WA 了很多次因为数组开小了和没开 long long,就让人不开心了(垃圾题面没有边权范围)。假设我们有三个点 A、B、C,其中 A 和 B 有一个权值为 v1 的边,B 和 C 有一个权值为 v2 的边,我们把 B 拆成两个点 B1,B2,其中 B1 连 A,B2 连 C,我们假设 v1 < v2,于是我们可以这样开始连边:B1 连 B2 权值为 v2 - v1B2 连 B1 权值为 0A 连 B1 权值为 v1B1 连 A 权值为 0C 连 B2 权值为 v2B2 连 C 权值为 0好好思考一下这种建图方- 阅读剩余部分 -

BZOJ 4152: [AMPPZ2014]The Captain

Solution我们可以发现如果有三个点的 x1 <= x2 <= x3,那么 x1 和 x3 两个点不需要连边,对于 y 也是同样的道理,所以排序后连边跑最短路就可以了。Code#include <cstdio> #include <algorithm> #include <iostream> #include <cstring> #include <set> using namespace std; const int N = 1000010; struct node {int x, y, id;}- 阅读剩余部分 -

BZOJ 3891: [Usaco2014 Dec]Piggy Back

题目描述给定一个N个点M条边的无向图,其中Bessie在1号点,Elsie在2号点,它们的目的地为N号点。Bessie每经过一条边需要消耗B点能量,Elsie每经过一条边需要消耗E点能量。当它们相遇时,它们可以一起行走,此时它们每经过一条边需要消耗P点能量。求它们两个到达N号点时最少消耗多少能量?输入The first line of input contains the positive integers B, E, P, N, and M. All of these are at most 40,000. B, E, and P are described abov- 阅读剩余部分 -

BZOJ 3299: [USACO2011 Open]Corn Maze玉米迷宫

Description今年秋天,约翰带着奶牛们去玩玉米迷宫。迷宫可分成NxM个格子,有些格子种了玉 米,种宥玉米的格子无法通行。 迷宫的四条边界上都是种了玉米的格子,其屮只有一个格子 没种,那就是出口。 在这个迷宫里,有一些神奇的传送点6每个传送点由一对点组成,一旦 走入传送点的某个结点, 机器就会强制把你送到传送点的另一头去。所有的传送点都是双向 的,如果你定到了另一头,机器也会把你送回来。 奶牛在一个单位的时间内只能向相邻的四个方向移动一格,不过传送机传送是瞬间完成 的。 现在W西在迷宫里迷路了,她只知道目前的位罝在哪里,请你帮助她用最短的时间走出 迷宫吧。Input第- 阅读剩余部分 -

BZOJ 3393: [Usaco2009 Jan]Laserphones 激光通讯

DescriptionInput第1行输入w和H,之后W行H列输入地图,图上符号意义如题目描述.Output最少的对角镜数量.Sample Input7 8 ....... ......C ......* *****.* ....*.. ....*.. .C..*.. .......Sample Output3Solution搜索,类似于最短路,不过要加一维方向,整体类似于 SPFACode#include <bits/stdc++.h> #define long long long using namespace std; inline void read(i- 阅读剩余部分 -

BZOJ 3018: [Usaco2012 Nov]Distant Pastures

Description给定一个n×n的一个网格,每个格子有一个字符,要么是’(‘,要么是’)’。每个格子和它的上下左右的四个格子相邻,对于相邻的两个格子x和y,从x走到y的过程中,如果x和y中的字符相同,消耗A单位时间,如果x和y中字符不同,消耗B单位时间。定义点S到点T的时间为D(S,T),现在想请你求出网格中最大的D(S,T)。Input第一行三个整数n,A,B;接下来n行描述这个n×n的网格。1 <= n <= 30,1 <= A <= 1,000,000,1 <= B <= 1,000,000。Output一个整数,最大的D(S,- 阅读剩余部分 -

BZOJ 1774: [Usaco2009 Dec]Toll 过路费

Description跟所有人一样,农夫约翰以着宁教我负天下牛,休叫天下牛负我的伟大精神,日日夜夜苦思生 财之道。为了发财,他设置了一系列的规章制度,使得任何一只奶牛在农场中的道路行走,都 要向农夫约翰上交过路费。 农场中由N(1 <= N <= 250)片草地(标号为1到N),并且有M(1 <= M <= 10000)条 双向道路连接草地A_j和B_j(1 <= A_j <= N; 1 <= B_j <= N)。奶牛们从任意一片草 地出发可以抵达任意一片的草地。FJ已经在连接A_j和B_j的双向道路上设置一个过路费L_j (- 阅读剩余部分 -

BZOJ 4102: [Usaco2015 Open]Bessie

Description为了庆祝贝茜的生日,FJ给她吃草的自由. N块草地,标号1到N(1<=N<=1000),草地有营养价值.当贝茜走到这个草地,可以获得等于这块草地的营养价值的能量. 每块草地最多有10条双向边,每走一条边,贝茜花费E的能量. 贝茜拿可以从任何地方出发,当她不能获得更多的能量的时候她就会停止. 然而因为贝茜挑食,她每次不会吃低于或等于上次的营养价值的草地,所以她获得的能量是严格上升的,当然她可以选择只是经过一块草地而不吃草.算出贝茜能够获得的最大能量.Input第一排两个数 N和E剩下N排,每排包含Q,D两个数字,Q代表这个草地的营养价值,D代- 阅读剩余部分 -

BZOJ 3445: [Usaco2014 Feb] Roadblock

Description有一个无向图,共N个节点,编号1至N,共M条边。FJ在节点1,它想到达节点N。FJ总是会选择最短路径到达节点N。作为捣蛋的奶牛Bessie,它想尽量延迟FJ到达节点N的时间,于是Bessie决定从M条边之中选择某一条边,使得改边的长度变成原来的两倍,由于智商的问题,Bessie不知道选择加倍哪条边的长度才能使得FJ到达N号节点的时间最迟。注意:不管Bessie选择加倍哪条边的长度,FJ总是会从1号节点开始走最短路径到达N号点。Input第一行,两个整数N和M. 1 <=N<=250, 1<=M<=250000。 接下来有M行,每- 阅读剩余部分 -

BZOJ 1598: [Usaco2008 Mar]牛跑步

DescriptionBESSIE准备用从牛棚跑到池塘的方法来锻炼. 但是因为她懒,她只准备沿着下坡的路跑到池塘, 然后走回牛棚. BESSIE也不想跑得太远,所以她想走最短的路经. 农场上一共有M (1 <= M <= 10,000)条路, 每条路连接两个用1..N(1 <= N <= 1000)标号的地点. 更方便的是,如果X>Y,则地点X的高度大于地点Y的高度. 地点N是BESSIE的牛棚;地点1是池塘. 很快, BESSIE厌倦了一直走同一条路.所以她想走不同的路,更明确地讲,她想找出K (1 <= K <= 100)条不同- 阅读剩余部分 -

BZOJ 2763: [JLOI2011]飞行路线

DescriptionAlice和Bob现在要乘飞机旅行,他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务,设这些城市分别标记为0到n-1,一共有m种航线,每种航线连接两个城市,并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市,途中可以进行转机。航空公司对他们这次旅行也推出优惠,他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少?Input数据的第一行有三个整数,n,m,k,分别表示城市数,航线数和免费乘坐次数。第二行有两个整数,s,t,分别表示他们出行的起点城市编号和终点城市编号。(0<=- 阅读剩余部分 -