当前位置: 首页 > news >正文

百度爱采购怎么免费入驻win7优化大师下载

百度爱采购怎么免费入驻,win7优化大师下载,公司网站建设的分类,矿业公司网站源码题目 给出 n 个点的一棵树,多次询问两点之间的最短距离。 注意: 边是无向的。所有节点的编号是 1,2,…,n。 输入格式 第一行为两个整数 n 和 m。n 表示点数,m 表示询问次数; 下来 n−1 行,每行三个整数 x,y,k&am…

题目

给出 n 个点的一棵树,多次询问两点之间的最短距离。

注意:

  • 边是无向的。
  • 所有节点的编号是 1,2,…,n。
输入格式

第一行为两个整数 n 和 m。n 表示点数,m 表示询问次数;

下来 n−1 行,每行三个整数 x,y,k,表示点 x 和点 y 之间存在一条边长度为 k;

再接下来 m 行,每行两个整数 x,y,表示询问点 x 到点 y 的最短距离。

树中结点编号从 1 到 n。

输出格式

共 m 行,对于每次询问,输出一行询问结果。

数据范围

2 ≤ n ≤ 10^4
1 ≤ m ≤ 2 × 10^4
0 < k ≤ 100
1 ≤ x , y ≤ n

思路

 我们以以下样例来建一张图

样例:
10 0
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
8 10

        首先我们假定点1为根节点,求出所有节点到点1的最短距离dist[ j ]。 

        我们可以假设点1为根节点,往下深度优先遍历每一个节点,只有当某一个节点的所有子节点都被便利之后才会更新其祖先节点,所以在这个点 a 的所有子节点没有遍历结束之前, a 的所有子节点的祖先都是节点 a 。易得,当求的两个点 x , y 都是属于点 a 的孙子结点的时候,x与y的距离为dist[ i ] + dist[ j ] - dist[ a ] * 2;

代码 

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 20010, M = N * 2;int n,m;
int h[N],e[M],w[M],ne[M],idx;
int res[N];
int dist[N];
int st[N];
int p[N];
vector<PII> query[N];void add(int a,int b,int c)// 加点函数,使用邻接表储存该图
{e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx ++;
}int find(int x)// 并查集板子
{if(p[x] != x) p[x] = find(p[x]);return p[x];
}void dfs(int u,int fa)// 初始每个点到根节点的距离
{for(int i = h[u]; ~i ; i = ne[i]){int j = e[i];if(j == fa) continue;// 因为是无向边,所以会有一条边指向该点的父节点。dist[j] = dist[u] + w[i];// 子节点距离根节点的距离为父节点加上父节点到该点的距离dfs(j,u);//使用该点继续初始其他节点}
}void tarjan(int u)// 该题核心函数
{st[u] = 1;for(int i = h[u];~i; i = ne[i])// 每个点的祖先都是它的父节点{int j = e[i];if(!st[j]){tarjan(j);// 以j为祖先节点,遍历所有j的所有子节点p[j] = u;//将点j的所有子节点遍历完成之后,就更新点j的祖先节点}}for(auto item : query[u]){int y = item.first,id = item.second;if(st[y] == 2)// 如果点y已经完成遍历,则可以进行求距离操作{int anc = find(y);res[id] = dist[u] + dist[y] - dist[anc] * 2;}}st[u] = 2;//表示该点祖先节点已经更新,且所有子节点都已经完成遍历
}int main()
{cin >> n >> m;memset(h,-1,sizeof(h));for(int i = 1; i < n; i ++)//输入n-1条无向边{int a,b,c;cin >> a >> b >> c;add(a,b,c),add(b,a,c);}for(int i = 0; i < m; i ++)//输入m个询问{int a,b;cin >> a >> b;if(a == b) continue;query[a].emplace_back(b,i);query[b].emplace_back(a,i);}for(int i = 1; i <= n; i ++) p[i] = i;// 并查集初始化每个点所属的集合dfs(1,-1);// 假设点1为该树的根节点tarjan(1);for(int i = 0; i < m; i ++) cout << res[i] << endl;return 0;
}

http://www.sczhlp.com/news/45547/

相关文章:

  • 建设网站总结报告软文营销广告
  • 大理如何做百度的网站深圳网站seo
  • 网站建设论文结束语百度官网认证价格
  • 国企集团门户网站建设方案百度账号注册申请
  • 绿色环保网站模板今天上海最新新闻事件
  • Cisco Firepower 1000 Series FTD Software 7.7.10 发布 - 思科下一代防火墙系统软件
  • PVS‑Studio 7.38 for macOS, Linux Windows - 代码质量安全静态分析
  • Cisco Secure Firewall Threat Defense Virtual 7.7.10 - 思科下一代防火墙虚拟设备 (FTDv)
  • 手机版商城网站都有哪 些功能今日重大新闻头条十条
  • 铜陵58同城做网站域名解析ip地址
  • 平面设计资源网站查数据的网站有哪些
  • b站推广网站2024不用下载谷歌推广代理商
  • 页游源码论坛台州seo优化公司
  • WinGet 在涉及查询应用的命令时,会处于长时间加载,无法进行下一步操作
  • 推荐一款基于 Python 和 Rust 开发的跨平台 GUI 自动化库!
  • 站长工具seo综合查询下载安装百度信息流推广是什么意思
  • 网站模板制作流程免费职业技能培训网站
  • 乌鲁木齐网站建设求职简历电话营销
  • 深圳app网站建设陈俊兵会计培训
  • 网站搭建教学网自己怎么做网站
  • 江苏苏州建设行政主管部门网站站长之家关键词挖掘
  • 互联网网站如何做推广软文案例
  • 建设网站多久营销策略模板
  • ico加网站衡水网站优化推广
  • 网站开发外包合同模板廊坊百度快照优化哪家服务好
  • seo是做网站源码还是什么品牌推广策划方案
  • 做企业网站需要哪些百度快速排名案例
  • 网站的日志文件竞价软件哪个好
  • 什么项目适合新手创业湖南关键词优化首选
  • 做中医诊所网站上海seo关键词优化