喊山 BFS

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头，本题请你找出这个信号最远能传达到的地方。

输入格式：

输入第一行给出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一开始有两种想法 dfs bfs和最短路我嫌bfs麻烦就开了最短路
因为是不能绕行的比如1，2，3互相连
不能是1到2再到3 所以dfs行不通
这恰巧就是最短路的不断优化。。
做到最后光荣的拿了17分这么简单的题只拿了17分 QwQ
因为比赛的时候没时间了
提一下这次周练时间不够 3小时6题天梯三十分的题目我们这些弱鸡没有一个ak（我还有一题没开其他题都是。。没怎么满分）除了队里第一的大佬 30分钟内ak全部蒟蒻的我怀疑人生dijkstra ：补了并查集还是没过。。

#include<bits/stdc++.h>
using namespace std;
//input
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m);
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
#define N 10005
#define inf 0x3f3f3f3f
int n,m,q;
int mp[N][N];
int dis[N];
int vis[N];int f[];
int find1(int x)
{
int j=x;
while(j!=f[j])
j=f[j];
int cur=x;
if(cur!=j)
{
int t=f[cur];
f[cur]=j;
cur=t;
}
return j;
}
void union1(int x,int y)
{
int x1=find1(x);
int y1=find1(y);
if(x1<y1)f[y1]=x1;
else f[x1]=y1;
return ;
}void dijkstra(int s)
{
memset(vis,,sizeof vis); for(int i=;i<=n;i++)
{
dis[i]=mp[s][i];
if(find1(i)!=find1(s))vis[i]=;
}
dis[s]=;
vis[s]=; for(int i=;i<=n;i++)
{
int minn=inf,u=-;
for(int j=;j<=n;j++)
if(!vis[j]&&minn>dis[j])
minn=dis[u=j];
if(u==-)return;
vis[u]=;
for(int j=;j<=n;j++)
{ if(dis[j]>dis[u]+mp[u][j])
dis[j]=dis[u]+mp[u][j]; }
}
}int main()
{
RIII(n,m,q);
for(int i=;i<=n;i++)
f[i]=i;
rep(i,,n)
rep(j,,n)
if(i==j)mp[i][j]=;
else mp[i][j]=inf; while(m--)
{
int a,b;
RII(a,b);
union1(a,b);
mp[a][b]=mp[b][a]=;
} while(q--)
{
int x;
RI(x);
dijkstra(x);
int maxx=; int flag=;
rep(i,,n)
if(dis[i]<)
if(dis[i]>maxx)maxx=dis[i],flag=i; cout<<flag<<endl;
}
return ;
}