【CodeVS 2602 最短路径问题】

【CodeVS 2602 最短路径问题】

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

【Date】

【问题描述】 小SYH和小LCR好不容易有机会约会啦,可是邪恶的小YJQ却不想让他们相见。现在有一些城市,城市之间有双向路径相连,有路径相连的城市之间可以互相到达。小YJQ可以任意选择一条路径,然后用他FFF团的怒火烧毁这条路径,使得它不能被通行。虽然小SYH和小LCR在千辛万苦之后相遇了,但是小LCR非常害怕。她想让小SYH告诉她,他们初始在哪些点对上,小...
【Isfind】

【Isfind】

【问题描述】 给出一个长度为n的字符串S,给出m组询问,每次询问给出一个非空字符串,判断这个字符串是否是S的子序列,如果是,那么输出“Y”,否则输出”N” 【输入格式】 第一行两个数n,m,分别表示字符串长度以及询问数。 下一行一个长度为n的字符串S。 接下来m行,每行一个询问的非空字符串。 【输出格式】 输出共m行,每行一个大写字母...
【受欢迎的牛】

【受欢迎的牛】

题目描述 每一头牛的愿望就是变成一头最受欢迎的牛。现在有 N 头牛,给你 M 对整数(A,B),表示牛A认为牛B受欢迎。这种关系是具有传递性的,如果 A 认为 B 受欢迎,B 认为 C 受欢迎,那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。 输入格式 第一行两个数 N,M 。 接下来 M 行,每行两个数 A,B,意思是 A...
【Road】

【Road】

【问题描述】 给出一张n个点,m条边的无向图,摧毁每条边都需要一定的体力,并且花费的体力值 各不相同,给定图中两个点x,y(x≠y),每当(x,y)之间存在路径,就需要不断摧毁当前 图中花费体力最少的一条边,直到该路径不联通。他定义cost(x,y)为摧毁(x,y)之间路径 花费的体力和。 他想要求出这个结果: 【输入格式】 第一行两个整数n,m,表示点数...
【Xor】

【Xor】

【问题描述】 求一颗带边权的树的一条最大Xor路径的值。 【输入格式】 第一行,一个整数N,表示一颗树有N个节点,接下来N-1行,每行三个整数a b c表示节点a和节点b之间有条权值为c的边。 【输出格式】 输出仅一行,即所求的最大值。 【输入样例】 4 1 2 3 1 3 4 1 4 7 【输出样例】 7 【数据范围】 对于100%的数据:1≤N≤1000...
【Tree】

【Tree】

【题目描述】 给你一堆边,其中有些边为黑色,有些边为白色,每条边有一条边权。 这些边一定能构造成一颗树,请问其中恰好选K条白边的最小生成树的权值和是多少? 【输入格式】 第一行三个整数n m k表示点数,边数,以及K 接下来m行每行四个整数u v w c表示u到c有一条权值为w颜色为c(0为白色1为黑色)的边(双向边) 【输出格式】 一行一个整数,表示恰好选...
【Snow】

【Snow】

【问题描述】 有一天,YJQ要去登门造访ZZY家。ZZY的大门外有n个站台,用1到n的正整数编号,YJQ需要对每个站台访问恰好一定次数以后才能到YYY家。站台之间有m个单向的传送门,通过传送门到达另一个站台不需要花费任何代价。而如果不通过传送门,YJQ就需要乘坐公共汽车,并花费1毛钱。值得庆幸的是,任意两个站台之间都有公共汽车直达。 现在给定每个站台必须访问...
【树边的和】

【树边的和】

【问题描述】 树是指由n个点,n-1条边构成的联通无向图。如果有一棵树,它的每一条边(u,v)都有一个权值l(u,v),我们把这样的树称作带权树。 我们知道对于树上的任意两个点,他们之间的路径是唯一的。对于两个点u,v来说,我们可以算出u与v之间的路径上的所有边权之和,将其称作u与v之间路径的长度,记作d(u,v)。 你的任务是计算:∑d(u,v) (u!=...
【Proof】

【Proof】

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