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

全栈程序员-站长 • 2022年8月9日上午7:36 • 未分类 • 阅读 6

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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。

输入样例：

输出样例：

题解
堆优化版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;
    }
}