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

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