首页 > 试题广场 >

良心送分题

[编程题]良心送分题

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

注：本题所有边的边权均为 ${1}$ ,下文将不再提及。
给定一棵 ${n}$ 个点的树 ${G=<V,E>}$ ,现在通过以下规则创造一个 ${n\times k}$ 个点的图 ${G'=<V',E'>}$
将 ${G'}$ 的点分为 ${k}$ 组，每组 ${n}$ 个点，每个点的标号为 ${(a,b)}$ ，表示这是第 ${a}$ 组第 ${b}$ 个点。
${G'}$ 中存在边 $((a_{1},b_{1}),(a_{2},b_{2}))$ 当且仅当 ${a_{1}=a_{2}}$ 且边 $(b_{1},b_{2})∈E$
构造完 ${G'}$ 之后，我们再向其中加入另外的 ${m}$ 条边，第 ${i}$ 条边连接点 $(x_{i},y_{i})$ 和点 $({z_{i},w_{i}})$ 。
最后，请你求出点 ${(sa,sb)}$ 至点 ${(ta,tb)}$ 的最短路

输入描述:

第一行数字
接下来行，每行两个数字，表示树中的一条边
接下来行，每行四个数字，表示一条被添加的边
接下来一行四个数字。

输出描述:

一行一个数字表示答案，若与不连通则输出

示例1

输入

输出

备注:


保证答案在int范围内，可能有重边

算法知识视频讲解

WuliWuliiii

发表于 2019-12-21 12:51:45

先发一下我的CSDN博客哟：https://blog.csdn.net/qq_41730082/article/details/103643159 首先，这道题的思维展开，肯定不能把所有的点都用进来，那么，选择的点，我们可以只考虑起点和终点还有特殊的像M条链接边的点了，所以，点数的上限就是1e5，展开全文