题意简洁明了， 数据级别，直接排除了多源最短路的算法，值得一提的是， 十分奇特，一棵树的边是 ，我们可以将这个图看成一棵树加上100条以内的边的图。先考虑一棵树，如何求两点距离？我们需要前置知识点：LCA（最近公共祖先）红色框框的两个节点u,v，求他们的距离，看他们的深度:depth[u]=4，de
展开全文
题目链接 题意：题解： AC代码 /*
Author : zzugzx
Lang : C++
Blog : blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#
展开全文
题意 给一个连通图，每次询问两点间最短路。 分析 首先我们取联通的条边，利用，处理出询问的答案。 然后我们最多还剩下条边，我们对这些边的点跑，处理出所有点到该点的距离，然后遍历所有的询问，更新答案。 时间有点紧 #include <bits/stdc++.h>
using namespa
展开全文
题目描述n 个点，m条边， q个询问 ，每次输出 x,y的最短距离 思路首先看一个弱化版的给你n个点 ，n-1条边构成一颗树，q个询问，每次输出树上两点x,y的距离 这个题就是一个裸的LCA，lca的dfs完之后可以直接输出 int dis(int x, int y) {
return de
展开全文
NC19814 最短路 题目地址： https://ac.nowcoder.com/acm/problem/19814 基本思路： 题意很明了就是让我们每次在图中查询任意两点的最短路。数据范围很大肯定不能使用算法，而且也不是树同样也不能使用快速求树上距离，但是题目保证了图联通，而且数据范围里
展开全文
题意： 给定一个个点条边的无向连通图，所有边边权均为，次询问，每次询问图中两点的最短路径，保证无自环与重边。数据范围： 题解：由于是无向连通图，一眼看上去是一个不可做题。卡了很久很久才发现了数据范围有点不寻常，考虑最多有条多余的边，其余边可以组成一棵树。那么如果是一棵树则可以先预处理后用，本题相较于
展开全文
700ms飘过你可能不相信 我先加了inline又加了快读。。。然后TLE->AC题意：第一行两个整数n和m，表示图的点数和边数（1≤ n≤ 100000, 1≤ m≤ n+100）。接下来m行每行两个整数a和b，表示一条边（1≤ a, b≤ n）。保证没有自环和重边。保证图连通。接下来一个整
展开全文
思路： 因为边的数量最多比点多100个，所以先把多余的那些边去掉，用lca计算最短路，然后再把多余的边加上，再对这些多余的边进行bfs。去掉和加上多余边的方法：在存图的时候，利用并查集判断一下，如果这两个点有同一个父亲节点，那就证明这个边是多余的，就先把它给存起来而不加到图里。 #include &
展开全文
题目描述 给一个连通图，每次询问两点间最短路。每条边的长度都是1。 输入描述: 第一行两个整数n和m，表示图的点数和边数（1≤ n≤ 100000, 1≤ m≤ n+100）。接下来m行每行两个整数a和b，表示一条边（1≤ a, b≤ n）。保证没有自环和重边。保证图连通。接下来一个整数q表示
展开全文
题目意思 给出n个点，最多只会有n+100条边，问给出q次询问，每次询问的两个点最短距离是什么，规模都是1e5 解题思路 第一想法：floyd算法，再看下问题规模，1e5，因为floyd基于邻接矩阵存储而且要On^3空间时间都不满足。 换个方向，题目给出的数据范围要仔细琢磨，最多的只有n+100条边
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
