How far away ? 【HDU - 2586】【DFS+链式前向星优化】

2023-11-18

题目链接


  其实这道题可以不用链式前向星优化换做vector<>也是可以跑的,只是会许会慢些而已。


来换个中文题意好读些

勇气小镇是一个有着n个房屋的小镇,为什么把它叫做勇气小镇呢,这个故事就要从勇气小镇成立的那天说起了,
修建小镇的时候,为了让小镇有特色,镇长特地只修了n-1条路,并且规定说,所有在勇气小镇的村民,每一次出门必须规划好路线, 
路线必须满足在到达终点之前绝对不走回头路。每个人都要这样,不然那个人就不配在小镇生活下去,因为他没有这个勇气。
事实上,这并不能算一项挑战,因为n-1条路已经连通了每户人家,不回头地从起点到终点,只是一个时间上的问题。
由于小镇上的福利特别好,所以小懒入住了这个小镇,他规划了m次的行程,每次从L房屋到R房屋,他想问你他每次从L房屋到R房屋需要走多远的路。

Input

输入的第一行是一个整数t,表示有t组数据
   每组数据第一行是n,m两个数字,分别表示小镇上房屋的个数,和小懒计划的行程的数量。
之后第2行到第n行,每行三个整数a,b,c表示,a房屋与b房屋之间连接着一条距离为c的小路。
第n+1行到第n+m行,每行两个整数,L,R,代表一次小懒的询问,也就是询问小懒从L房屋走到R房屋所走的最近距离为多少。

Output

对于每组测试数据输出m行,每行一个整数,代表小懒从询问的L到R需要走的最近的距离


  直接DFS去搜索何时能抵达目标节点即可,毕竟只有M条边的上限的嘛,时间复杂度一定是可以跑的。


#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN=40005;
int N, M, head[maxN], cnt;
bool vis[maxN];
struct Eddge
{
    int next, to, val;
    Eddge(int a=-1, int b=0, int c=0):next(a), to(b), val(c) {}
}edge[maxN<<1];
void addEddge(int u, int v, int val)
{
    edge[cnt] = Eddge(head[u], v, val);
    head[u] = cnt++;
}
void init()
{
    cnt = 0;
    memset(head, -1, sizeof(head));
}
bool flag;
void dfs(int now, int ed, ll cost)
{
    if(flag || vis[now] || head[now]==-1) return;
    vis[now] = true;
    if(now == ed) { printf("%lld\n", cost); flag=true; return; }
    for(int u=head[now]; u!=-1; u=edge[u].next)
    {
        dfs(edge[u].to, ed, cost+edge[u].val);
    }
}
int main()
{
    int T;  scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &N, &M);
        init();
        for(int i=1; i<=N-1; i++)
        {
            int e1, e2, e3;
            scanf("%d%d%d", &e1, &e2, &e3);
            addEddge(e1, e2, e3);
            addEddge(e2, e1, e3);
        }
        for(int i=1; i<=M; i++)
        {
            int l, r;
            scanf("%d%d", &l, &r);
            memset(vis, false, sizeof(vis));
            flag = false;
            dfs(l, r, 0);
        }
    }
    return 0;
}

 

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

How far away ? 【HDU - 2586】【DFS+链式前向星优化】 的相关文章

  • hdu 5756:Boss Bo

    题目链接如下 Problem 5756 先用dfs确定每个节点的序号编号 并且可以获得每个节点可以包括的子树节点区间范围 再用线段树建立一棵树 在第一次建立的时候我们记录每个节点的深度 然后再进行一次dfs 这次dfs用来更新以不同节点为根
  • Codeforces Round 867 (Div. 3)(A题到E题)

    链接 Dashboard Codeforces Round 867 Div 3 Codeforces 头一次div3做出来四题 第五题也差临门一脚 赛后看到别人e题跟自己几乎一样的思路肠悔青了 还得练才行 A TubeTube Feed 签
  • 图论17(Leetcode864.获取所有钥匙的最短路径)

    用二进制表示获得的钥匙 假设n 钥匙个数 000000000代表没有钥匙 0000000001代表有idx为1的钥匙 0000000011代表有idx 1 2的钥匙 这方法巧妙又复杂 代码 class Solution static int
  • 西安电子科技大学第二届程序设计新生赛-F-zxy的长跑【欧拉回路】

    题目链接 好极了的欧拉回路 我们想知道怎样才能跑完所有的边 我们可以从度为奇数的点出发 因为这是欧拉回路的无向图的先觉调节 当然 这道题还有另外一种可能就是这是一个环 1 gt 2 2 gt 3 3 gt 4 4 gt 1 那么就没有奇数度
  • 图的应用--Prim算法

    图的应用 Prim算法 Prim算法是一种基于顶点的贪心算法 从起始顶点出发 每次迭代选择当前可用的最小权值边 然后把边上依附的其他顶点加入最小生成树 prim算法可以称为 加点法 比较适合稠密图 算法思想 设G V E 是一个加权连通图
  • 大学生团体天梯赛(第十届)

    题目地址 天梯赛 include
  • 【DFS和BFS习题集+分类总结】(更新至2023.1.1)(17788字)

    目录 第一题 八皇后 dfs 路径输出 前驱版 第一题的补充练习 N皇后 dfs 打表 第二题 自然数的拆分 第三题 图的遍历 BFS和DFS 第四题 fire net dfs 第五题 nightmare 可以走回头路的DFS 第六题 滑雪
  • 大学生团体天梯赛(第五届)

    题目地址 天梯赛 include
  • AcWing 378. 骑士放置(最大独立集&&匈牙利算法)

    输入样例 2 3 0 输出样例 4 解析 题意为求最大独立集 即为总点数 最小点覆盖 include
  • [UVA1364

    评测地址 网址1 网址2 题目描述 题意 给出n位骑士 然后有m个关系 每个关系以格式 a b a b a b给出 表达骑士 a a
  • [ACM] 1016 Prime Ring Problem (深度优先搜索)

    Prime Ring Problem Problem Description A ring is compose of n circles as shown in diagram Put natural number 1 2 n into
  • Summer Holiday HDU - 1827 强连通分量+缩点

    To see a World in a Grain of Sand And a Heaven in a Wild Flower Hold Infinity in the palm of your hand And Eternity in a
  • 蓝桥杯 题库 简单 每日十题 day2

    01 卡片 题目描述 本题为填空题 只需要算出结果后 在代码中使用输出语句将所填结果输出即可 小蓝有很多数字卡片 每张卡片上都是数字 0 到 9 小蓝准备用这些卡片来拼一些数 他想从 1 开始拼出正整数 每拼一个 就保存起来 卡片就不能用来
  • 仙岛求药 —— dfs 与 bfs求解

    样例输入1 8 8 样例输出1 10 样例输入2 9 6 样例输出2 1 dfs ps 使用dfs会运行超时 30组测试数据只能通过部分 其实这种最短路径 最少操作的问题最好还是靠bfs解决 import java util Scanner
  • Two Arithmetic Progressions

    Two Arithmetic Progressions 题目链接 题意 思路 AC代码1 include
  • 无向图染色问题-dfs剪枝

    无向图染色问题 问题描述 给定一个无向图 要求用最少的颜色将节点染色 限制是不能让相邻节点染上相同的颜色 算法 使用dfs 为节点分配不同的颜色进行尝试 计算每种分配所需的颜色数 最终进行回溯 取得最小的颜色数 代码 C include
  • 图论--最近公共祖先LCA

    最近公共祖先LCA LCA Least Common Ancestors 即最近公共祖先 是指这样一个问题 在有根树中 找出某两个结点u和v最近的公共祖先 另一种说法 离树根最远的公共祖先 最近公共祖先是相对于两个节点来说的 一般来说 最近
  • 迷宫问题java老鼠走迷宫(回溯法,递归,二维数组)(超级容易理解)

    回溯法迷宫问题 思路 利用回溯法和递归思想解决 findWay 方法就是专门来找出迷宫的路径 如果找到 就返回 true 否则返回 false map 就是二维数组 即表示迷宫 i j 就是老鼠的位置 初始化的位置为 1 1 因为我们是递归
  • 基于振动传感器数据构建预测性维护AI模型

    预测性维修 Predictive Maintenance 简称PdM 是以状态为依据 Condition Based 的维修 在机器运行时 对它的主要 或需要 部位进行定期 或连续 的状态监测和故障诊断 判定装备所处的状态 预测装备状态未来
  • E (1052) : DS树--带权路径和

    文章目录 一 题目描述 二 输入与输出 1 输入 2 输出 三 参考代码 一 题目描述 计算一棵二叉树的带权路径总和 即求赫夫曼树的带权路径和 已知一棵二叉树的叶子权值 该二叉树的带权路径和APL等于叶子权值乘以根节点到叶子的分支数 然后求

随机推荐

  • Eclipse如何设置快捷键

    在eclopse设置注释行和取消注释行 打开eclipse 依次打开 Window gt Preferences gt General gt Key
  • Vue<router-view></router-view>学习心得

    今天看到个Vue项目结构中使用到了
  • C#基础教程(十四) String、StringBuilder、”==,equal,ReferenceEquals“

    1 内存分区 1 栈区 由编译器自动分配释放 存放值类型的对象本身 引用类型的引用地址 指针 静态区对象的引用地址 指针 代码中必须就栈的大小有明确的定义 栈区内存无需我们管理 也不受GC管理 栈顶元素使用完毕弹出就会立即释放 由操作系统管
  • 【0基础】学习solidity开发智能合约-初识solidity

    本篇课程开始 我们来学习一下如何使用solidity开发智能合约 由于博主对于solidity的学习 也是自学的 所以一些不足或有纰漏之处还望指出 大家共同进步 本系列课程会分很多节课讲述 从入门到进阶 实战 在课程最后 我们会通过所学知识
  • 【Py】给已存在的Excel添加sheet

    使用pandas import pandas as pd from openpyxl import load workbook df pd DataFrame a 1 book load workbook test xlsx with pd
  • GPT专业应用:生成会议通知

    正文共 917 字 阅读大约需要 3 分钟 公务员 文秘必备技巧 您将在3分钟后获得以下超能力 快速生成会议通知 Beezy评级 B级 经过简单的寻找 大部分人能立刻掌握 主要节省时间 推荐人 Kim 编辑者 Linda 图片由Lexica
  • vue、nuxt的mavon-editor富文本的使用及添加代码块高亮样式、代码块行数、一键复制代码功能

    为啥断更了这么久 就是因为mavon editor富文本框的样式 nuxt项目的seo nuxt项目的优化 nuxt首屏渲染等等等的问题导致这么久没有发文章了 这篇文章先讲vue项目及nuxt项目中使用mavon editor并改变代码块的
  • HTTPS 的加密流程

    目录 一 HTTPS是什么 二 为什么要加密 三 加密 是什么 四 HTTPS 的工作过程 1 对称加密 2 非对称加密 3 中间人攻击 4 证书 总结 一 HTTPS是什么 HTTPS Hyper Text Transfer Protoc
  • BUUCTF-PWN-Writeup-1-5

    前言 开始刷一刷Buuctf的PWN题 一边学一边刷题了 其实主要是堆学的顶不住了 一个下午才搞懂一个知识点 太tm的难了 test your nc from pwn import from LibcSearcher import cont
  • 各大操作系统命令行清屏快捷键

    mac os x terminal清屏快捷键 cammand k linux系统清屏快捷键 ctrl l windows 命令行清屏命令 cls
  • 背景图片的定位问题详解

    我们在研究其他的网站的样式的时候经常会发现一种情况 就是在很多background属性里都调用同一张图片 来满足网页各个部分的使用 打开这种图片看一下 会发现这张图片上包含了很多小图片 比如 又如 这些小图片就是整图分割后的各个部分 把各个
  • Ubuntu16.04 获取Root 权限

    如果是第一次获得Root权限那么首先要设置root密码 sudo passwd root 获取root权限 su root 输入之前你设置的密码 退出root exit
  • Quartz教程--快速入门

    欢迎来到quartz快速入门教程 阅读本教程 你将会了解 quartz下载 quartz安装 根据你的需要 配置Quartz 开始一个示例应用 当熟悉了quratz调度的基本功能后 可以尝试一些更高级的特性 比如Where 这个一个企业级功
  • 深聊测试开发之:从订单支付流程来聊一聊,如何预防重复支付,建议收藏。

    如何预防订单重复支付 1 引言 2 订单支付流程 2 1 支付流程 2 2 订单状态 3 订单重复支付原因 3 1 掉单 3 2 未防重 3 3 多渠道 4 防止重复支付 4 1 加锁 4 2 缓存结果 4 3 支付中取消流水 4 4 已支
  • 微信小程序canvas画布绘制;canvas画布图片保存

    微信小程序canvas画布绘制 wx createSelectorQuery select canvas fields node true size true exec res gt let ctx res 0 node getContex
  • 关于域名暂时解析失败的问题 (Temporary failure in name resolution)

    相信很多小伙伴在运行爬虫程序的时候 都会遇到这么个错误 Temporary failure in name resolution 什么意思呢 昨天还运行的好好的呢 域名暂时解析失败 但是呢 在浏览器输入网址 还是可以打开这个网站的 看网站内
  • Win10开启高性能、卓越性能模式的方法

    Win10开启高性能 卓越性能模式的方法 一 老办法 1 打开PowerShell 管理员模式 Win X 选择 2 输入以下命令 powercfg duplicatescheme e9a42b02 d5df 448d aa00 03f14
  • MFC 动态链接库(DLL)中创建窗口失败

    毕业设计写一个关于网络的项目 在客户端把WSAAsyncSelect网络模型封装在了动态链接库中 点击运行 在UI线程中发现 创建一个CFrameWnd窗口的时候程序报错了 均显示ASSERT afxCurrentResourceHandl
  • LeetCode-450.删除二叉搜索树中的节点

    给定一个二叉搜索树的根节点 root 和一个值 key 删除二叉搜索树中的 key 对应的节点 并保证二叉搜索树的性质不变 返回二叉搜索树 有可能被更新 的根节点的引用 一般来说 删除节点可分为两个步骤 首先找到需要删除的节点 如果找到了
  • How far away ? 【HDU - 2586】【DFS+链式前向星优化】

    题目链接 其实这道题可以不用链式前向星优化换做vector lt gt 也是可以跑的 只是会许会慢些而已 来换个中文题意好读些 勇气小镇是一个有着n个房屋的小镇 为什么把它叫做勇气小镇呢 这个故事就要从勇气小镇成立的那天说起了 修建小镇的时