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+链式前向星优化】 的相关文章

  • CentOS 7.9 64位 SCC版安装FastDfs和配置Nginx

    最近练习的项目中需要用到FastDfs 和Nginx 这里记录一下安装和配置过程 个人使用部署过程遇到了很多的坑 准备把过程记下来不然忘了 首先 购买 试用阿里云 CentOS 7 9 64位Scc版系统 进入远程桌面 由于项目较老 所以我
  • 西安电子科技大学第二届程序设计新生赛-F-zxy的长跑【欧拉回路】

    题目链接 好极了的欧拉回路 我们想知道怎样才能跑完所有的边 我们可以从度为奇数的点出发 因为这是欧拉回路的无向图的先觉调节 当然 这道题还有另外一种可能就是这是一个环 1 gt 2 2 gt 3 3 gt 4 4 gt 1 那么就没有奇数度
  • 2021级新生个人训练赛第38场

    问题 A chicken 题目描述 小 x 非常喜欢小鸡翅 他得知 NSC 超市为了吸引顾客 举行了如下的活动 一旦有顾客在其他超市找到更便宜的小鸡翅 NSC 超市将免费送给顾客 1000g 小鸡翅 小 x 为了尽可能的省钱 走遍了各大超市
  • The Stable Marriage Problem 【HDU - 1914】【稳定婚姻匹配问题】

    题目链接 Problem Description The stable marriage problem consists of matching members of two different sets according to the
  • 深度、广度优先搜索

    文章目录 二 图的遍历 2 1 深度优先搜索 DFS DFS森林 应用 2 2 广度优先搜索 BFS 基本操作 应用 二 图的遍历 2 1 深度优先搜索 DFS DFS森林 Vertextype GetVex ALGraph G int v
  • 矩阵树定理

    启蒙 http zhengruioi com contest 1416 T1 T2的10分暴力 后面是论文科技 不搞了 https www luogu com cn problem P6178 O n 3
  • AcWing 378. 骑士放置(最大独立集&&匈牙利算法)

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

    评测地址 网址1 网址2 题目描述 题意 给出n位骑士 然后有m个关系 每个关系以格式 a b a b a b给出 表达骑士 a a
  • Leetcode【DFS BFS】

    Leetcode 200 岛屿数量 题目 解题 思路 DFS解法 BFS解法 题目 给你一个由 1 陆地 和 0 水 组成的的二维网格 请你计算网格中岛屿的数量 岛屿总是被水包围 并且每座岛屿只能由水平方向和 或竖直方向上相邻的陆地连接形成
  • LeetCode——1302. 层数最深叶子节点的和

    题目描述 给你一棵二叉树的根节点 root 请你返回层数最深的叶子节点的和 示例 1 输入 root 1 2 3 4 5 null 6 7 null null null null 8 输出 15 示例 2 输入 root 6 7 8 2 7
  • 仙岛求药 —— dfs 与 bfs求解

    样例输入1 8 8 样例输出1 10 样例输入2 9 6 样例输出2 1 dfs ps 使用dfs会运行超时 30组测试数据只能通过部分 其实这种最短路径 最少操作的问题最好还是靠bfs解决 import java util Scanner
  • 数据结构——图的DFS(深度优先遍历)- C语言代码实现

    图的深度优先遍历的基本思想 从图中某顶点v出发 1 访问顶点v 2 依次从v的未被访问的邻接点出发 对图进行深度优先遍历 直至图中和v有路径相通的顶点都被访问 3 若此时图中尚有顶点未被访问 则从一个未被访问的顶点出发 重新进行深度优先遍历
  • 714阿里巴巴模拟面试

    介绍一下数据库分页 https www nowcoder com questionTerminal 3577280c810546658f06f19c01ff0345 给定一棵树 求出这棵树的直径 即两个节点距离的最大值 应该是左右子树遍历深
  • 数据结构算法—邻接表存储的无向图求连通分量个数

    数据结构算法 邻接表存储的无向图求连通分量个数 邻接表存储结构 typedef struct ArcNode int adjvex 边指向的顶点 struct ArcNode nextarc 下一条边的指针 ArcNode typedef
  • 迷宫问题java老鼠走迷宫(回溯法,递归,二维数组)(超级容易理解)

    回溯法迷宫问题 思路 利用回溯法和递归思想解决 findWay 方法就是专门来找出迷宫的路径 如果找到 就返回 true 否则返回 false map 就是二维数组 即表示迷宫 i j 就是老鼠的位置 初始化的位置为 1 1 因为我们是递归
  • The Necklace 【UVA - 10054】【欧拉回路详解】

    题目链接1 题目链接2 题目求的是一串珠子 要让它们首尾相互照应才能串起来 并且 最后要连成一个环 使得最后的珠子的尾与第一个珠子的头相互对应 那么 这道题就是道求欧拉回路的题了 我们要先判断这是不是能够构成欧拉回路 这是个无向图 再对于需
  • Binary Tree on Plane【费用流】

    题目链接 CF 277 E 题意翻译 给你平面上 n 个点 2 n 400 要求用这些点组成一个二叉树 每个节点的儿子节点不超过两个 定义每条边的权值为两个点之间的欧几里得距离 求一个权值和最小的二叉树 并输出这个权值 其中 点 i 可以成
  • P1433 吃奶酪 题解(勿抄袭)

    P1433 吃奶酪 题目描述 房间里放着 n 块奶酪 一只小老鼠要把它们都吃掉 问至少要跑多少距离 老鼠一开始在 0 0 点处 输入格式 第一行一个正整数 n 接下来每行 2 个实数 表示第i块奶酪的坐标 两点之间的距离公式为 输出格式 一
  • DFS的个人理解和测试例题

    深度优先搜索 DFS 是一种搜索手段 可以理解为 它从某个位置 起点 开始 沿着一条路不断地向前走直到尽头 然后退后一步 去走其它没走过的路 没有的话 再退后一步 再去选择 直到找到目的地 终点 例如下图 从A 起点 开始走 先走ABD 在
  • 数模培训第二周——图论模型

    图论中最短路算法与程序实现 图论中的最短路问题 包括无向图和有向图 是一个基本且常见的问题 主要的算法有Dijkstra算法和Floyd算法 Floyd算法 简介 Floyd Warshall算法 英语 Floyd Warshall alg

随机推荐

  • 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个房屋的小镇 为什么把它叫做勇气小镇呢 这个故事就要从勇气小镇成立的那天说起了 修建小镇的时