大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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/168911.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...