【CodeVS 2602 最短路径问题】

【CodeVS 2602 最短路径问题】

题目描述 Description 平面上有n个点(n<=100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。 输入描述 Input Description 第一行为整数n。 第2行到第n+1...
【Proof】

【Proof】

【问题描述】 给出n条线段,每条线段有两个端点li和ri,选择这条线段需要花费costi,求连接区间[1,R]需要的最小花费。 【输入描述】 输入文件的第一行的两个整数R和n。 接下来n行,每行三个整数li,ri和costi,意义和问题描述一样。 【输出格式】 输出一个整数,表示最小花费。 如果不能覆盖全区间,输出-1. 【输入样例1】 9 3 1 3 10...
【Shortest】

【Shortest】

【问题描述】 给定一张n个点的有向带权完全图,和一个数组a[],请按顺序删除数组中的点,请求出删除点a[i]之前,所有未删除点对之间的最短路上的值的和。 【输入格式】 第一行一个整数n,表示点数; 接下来n行,每行n个数构成邻接矩阵,描述每条边的权值,保证i号点到i号点的权值为0; 最后一行n个小于等于n的不同的数,描述数组a[] 【输出格式】 输出1行n个...
【tree】

【tree】

【问题描述】 已知一棵n个节点的有根树。有m个询问。每个询问给出了一对节点的编号x和y,询问x和y的祖孙关系。 【输入格式】 输入第一行包括一个整数n表示节点个数。 接下来n行每一行一对整数对a和b表示a和b之间有连边。如果b是-1,那么a就是树的根。 第n+2行是一个整数m表示询问个数。 接下来m行,每行两个正整数x和y。 【输出格式】 对于每一个询问,输...
【Minimum】

【Minimum】

【问题描述】 给出一幅由n个点m条边构成的无向带权图。 其中有些点是黑点,另外点是白点。 现在每个白点都要与它距离最近的黑点通过一些边连接(就是最短路)(如果有很多歌,可以选取其中任意一个。),我们想要使得花费的代价最小。请问这个最小代价是多少? 【输入格式】 第一行两个整数n,m; 第二行n个整数,0表示白点,1表示黑点 接下来m行,每行三个整数x y z...
【第二短路】

【第二短路】

题目描述 贝茜把家搬到了一个小农场,但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景,不想那么快地结束她的旅途,于是她每次回农场,都会选择第二短的路径,而不象我们所习惯的那样,选择最短路。 贝茜所在的乡村有 R (1<=R<=100,000) 条双向道路,每条路都联结了所有的 N (1<=N<=5000) 个农场中的某两个...
【北京省选2012 冻结】

【北京省选2012 冻结】

题目背景 BJOI2012 第一轮 DAY2 T1 题目描述 我们考虑最简单的旅行问题吧:现在这个大陆上有 N 个城市,M 条双向的道路。城市编号为 1~N ,我们在 1 号城市,需要到 N号城市,怎样才能最快地到达呢? 这不就是最短路问题吗?我们都知道可以用 Dijkstra、Bellman-Ford、Floyd-Warshall 等算法来解决。 现...
【四川省选2011 糖果】

【四川省选2011 糖果】

题目背景 SCOI2011 DAY1 T1 题目描述 幼儿园里有 N 个小朋友,Lxhgww 老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心,总是会提出一些要求,比如小明不希望小红分到的糖果比他的多,于是在分配糖果的时候,Lxhgww 需要满足小朋友们的K个要求。幼儿园的糖果总是有限的,Lxhgww 想知道他至少...
【信号连接】

【信号连接】

题目描述 Nico 有一个排练室,她想把新买回来的 IMAX 银幕和放映机与远处的信号连接上,以便排练时可观看 lovelive 直播表演。 已知有 N 个信号发射仪,但其中只有 P 条线路能直接连接(Ai,Bi)(70%数据保证(A,B)只出现一次),且每条线路所花费的钱的就是该线路的长度 Li。保证源信号在 1 号点,排练室在 N 号点,且保证 1 和...
【Geodetic集合】

【Geodetic集合】

题目描述 图 G 是一个无向连通图,没有自环,并且两点之间至多只有一条边。我们定义顶点 v,u 最短路径就是从 v 到 u 经过边最少的路径。所有包含在 v-u 的最短路径上的顶点被称为 v-u 的 Geodetic 顶点,这些顶点的集合记作 I(v, u)。 我们称集合 I(v, u)为一个 Geodetic 集合。 例如下图中,I(2, 5)={2, ...
显示更多