L3-008 喊山(堆优化dijsktra+队列bfs)「建议收藏」

L3-008 喊山(堆优化dijsktra+队列bfs)「建议收藏」原题链接喊山,是人双手围在嘴边成喇叭状,对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递,回荡于深谷之间,传送到人们耳中,发出约定俗成的“讯号”,达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”,慢慢地人们在生活实践中发现了它的实用价值,便把它作为一种交流工具世代传袭使用。(图文摘自:http://news.xrxxw.com/newsshow-8018.html)一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

原题链接

喊山,是人双手围在嘴边成喇叭状,对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递,回荡于深谷之间,传送到人们耳中,发出约定俗成的“讯号”,达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”,慢慢地人们在生活实践中发现了它的实用价值,便把它作为一种交流工具世代传袭使用。(图文摘自:http://news.xrxxw.com/newsshow-8018.html)
在这里插入图片描述
一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头,本题请你找出这个信号最远能传达到的地方。

输入格式:
输入第一行给出3个正整数n、m和k,其中n(≤10000)是总的山头数(于是假设每个山头从1到n编号)。接下来的m行,每行给出2个不超过n的正整数,数字间用空格分开,分别代表可以听到彼此的两个山头的编号。这里保证每一对山头只被输入一次,不会有重复的关系输入。最后一行给出k(≤10)个不超过n的正整数,数字间用空格分开,代表需要查询的山头的编号。

输出格式:
依次对于输入中的每个被查询的山头,在一行中输出其发出的呼喊能够连锁传达到的最远的那个山头。注意:被输出的首先必须是被查询的个山头能连锁传到的。若这样的山头不只一个,则输出编号最小的那个。若此山头的呼喊无法传到任何其他山头,则输出0。

输入样例:

7 5 4
1 2
2 3
3 1
4 5
5 6
1 4 5 7

输出样例:

2
6
4
0

题解
堆优化版dijsktra

#include<bits/stdc++.h>
#define x first
#define y second
#define send string::npos
#define lowbit(x) (x&(-x))
#define left(x) x<<1
#define right(x) x<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef struct Node * pnode;
const int N = 2e5 + 10;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
const int Mod = 1e9;
int dis[N],vis[N];
int head[N],cnt;
int n,m,k,x,y;
priority_queue<PII,vector<PII>,greater<PII> > pq;
struct Edge{ 
   
    int v,next,w;
}edge[N];
void add(int u,int v,int w){ 
   
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
int dijstra(int s){ 
   
    memset(vis,0,sizeof vis);
    memset(dis,INF,sizeof dis);
    dis[s] = 0;
    pq.push({ 
   dis[s],s});
    while(!pq.empty()){ 
   
        PII t = pq.top();
        pq.pop();
        int ver = t.y;
        if(vis[ver])continue;
        vis[ver] = true;
        for(int i = head[ver];~i;i = edge[i].next){ 
   
            int v = edge[i].v,w = edge[i].w;
            if(dis[v] > dis[ver] + w){ 
   
                dis[v] = dis[ver] + w;
                pq.push({ 
   dis[v],v});
            }
        }
    }
    int pox = 0,d = 0;
    for(int i = 1;i <= n;i ++){ 
   
        if(dis[i] != INF && dis[i] > d){ 
   
            d = dis[i];
            pox = i;
        }
    }
    return pox;

}
int main(){ 
   
    memset(head,-1,sizeof head);
    cin>>n>>m>>k;
    int w;
    for(int i = 0;i < m;i ++){ 
   
        cin>>x>>y;
        add(x,y,1);
        add(y,x,1);
    }
    for(int i = 0;i < k;i ++){ 
   
        cin>>x;
        cout<<dijstra(x)<<endl;
    }
}

bfs版

#include<bits/stdc++.h>
#define x first
#define y second
#define send string::npos
#define lowbit(x) (x&(-x))
#define left(x) x<<1
#define right(x) x<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef struct Node * pnode;
const int N = 2e5 + 10;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
const int Mod = 1e9;
int dis[N],vis[N];
int head[N],cnt;
int n,m,k,x,y;
priority_queue<PII,vector<PII>,greater<PII> > pq;
struct Edge{ 
   
    int v,next;
}edge[N];
void add(int u,int v){ 
   
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}

int bfs(int x){ 
   
    memset(dis,INF,sizeof dis);
    memset(vis,0,sizeof vis);
    queue<int>q;
    dis[x] = 0;
    vis[x] = true;
    q.push(x);
    while(!q.empty()){ 
   
        int t = q.front();
        q.pop();
        for(int i = head[t];~i;i = edge[i].next){ 
   
            int ver = edge[i].v;
            if(!vis[ver]){ 
   
                vis[ver] = true;
                dis[ver] = dis[t] + 1;
                q.push(ver);
            }
        }
    }
    int pox = 0,d = 0;
    for(int i = 1;i <= n;i ++){ 
   
        if(dis[i] != INF && dis[i] > d){ 
   
            d = dis[i];
            pox = i;
        }
    }
    return pox;
}

int main(){ 
   
    memset(head,-1,sizeof head);
    cin>>n>>m>>k;
    int w;
    for(int i = 0;i < m;i ++){ 
   
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    for(int i = 0;i < k;i ++){ 
   
        cin>>x;
        cout<<bfs(x)<<endl;
    }
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169024.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • a 标签去掉下划线[通俗易懂]

    a 标签去掉下划线[通俗易懂]text-decoration:none

  • 数据归一化小结

    数据归一化小结在各种模型训练,特征选择相关的算法中,大量涉及到数据归一化的问题。比如最常见的情况是计算距离,如果不同维度之间的取值范围不一样,比如feature1的取值范围是[100,200],feature2的取值范围是[1,2],如果数据不做归一化处理,会造成feature1在距离计算中占压倒性的优势,feature2完全体现不出来作用。而数据做归一化处理以后,会让各个不同特征对距离计算的贡献大致相同,从而避

  • android scaleanimation 动画方向,Animation 动画详解(一)——alpha、scale、translate、rotate、set的xml属性及用法…[通俗易懂]

    android scaleanimation 动画方向,Animation 动画详解(一)——alpha、scale、translate、rotate、set的xml属性及用法…[通俗易懂]一、概述Android的animation由四种类型组成:alpha、scale、translate、rotate,对应android官方文档地址:《AnimationResources》alpha渐变透明度动画效果scale渐变尺寸伸缩动画效果translate画面转换位置移动动画效果rotate画面转移旋转动画效果下面我们逐个讲讲每个标签的属性及用法。动作定义文件应该存放在res/anim文…

  • 盘点当下大热的 7 大 Github 机器学习『创新』项目

    盘点当下大热的 7 大 Github 机器学习『创新』项目本文将会分享近期发布的七大GitHub机器学习项目。这些项目广泛覆盖了机器学习的各个领域,包括自然语言处理(NLP)、计算机视觉、大数据等。最顶尖的Github机器学习项…

  • scrollIntoView 实现「建议收藏」

    scrollIntoView 实现「建议收藏」1.应用场景: 相信大家都曾经遇到过要将屏幕的某一部分滚到到用户视窗里,例如聊天信息的自动滚屏等,这个有不少解决方案: 1.聊天面板的scrolltop=scrollheight2.消息最后加一个element,然后element.scrollIntoView但是如果想要任一容器中间的一个元素,滚到该容器的视窗显示部分…

  • pycharm中安装opencv_pycharm安装opencv库出错

    pycharm中安装opencv_pycharm安装opencv库出错Pycharm安装opencv的几种方法之前在默认环境中用pip安装过一次opencv,当时就是参考比人方法弄,稀里糊涂的,然后今天想在自己别的环境下(tensorflow)下安装终于弄懂了一些,暂时发现了几种安装的方法,特此记录下。方法1:在Pycharm自带的库中下载(暂且这么叫吧,如下图)这个方法我也是看别人说的,自己还没试过,描述也没介绍版本啥的,所以个人也不推荐…方法2:就是…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号