当前位置:网站首页>[unsolved] 7-15 shout mountain
[unsolved] 7-15 shout mountain
2022-07-06 16:45:00 【HBUcs2020】
Originally, I felt like 007 It's almost as deep into the tiger's den , Use vector and dfs Recursion is enough , Give it a try , It's my waste wood
#include<bits/stdc++.h>
using namespace std;
vector<int> q[10005];// use vector Array instead of adjacency table
int vis[10005], n, flag, mi, mi1;
queue<int> p;
void bfs(int u)
{
int i;
p.push(u);// Queue entry
vis[u] = 1;// The tag has been used ,1 On behalf of the first mountain left
while(!p.empty())// Not empty
{
u = p.front();// Take the first value of the team
p.pop();// Out of the team
if(vis[u] >= mi)// You have to walk at least two hills
{
if(vis[u] > mi)// to update mi, mi1
{
mi = vis[u];
mi1 = u;
}
else
{
mi1 = min(u, mi1);// Take the hill with the smallest number
}
}
for(i = 0; i < q[u].size(); i++)
{
if(!vis[q[u][i]])// by 0 It means you haven't walked
{
p.push(q[u][i]);// Queue entry
vis[q[u][i]] = vis[u] + 1;// to update vis value
}
}
}
}
int main()
{
int u, v, m, k;
while(~scanf("%d %d %d", &n, &m, &k))
{
while(m--)
{
scanf("%d %d", &u, &v);
q[u].push_back(v);// The subscript corresponding to the starting point , Deposit at destination
q[v].push_back(u);
}
while(k--)
{
mi = 2;// Number of hills
mi1 = 10005;// Number
memset(vis, 0, sizeof(vis));// Mark the mountain you have passed and judge how far you have gone
scanf("%d", &u);
bfs(u);
if(mi1 == 10005) printf("0\n");// There is no second mountain to walk
else printf("%d\n", mi1);
}
}
}
The first line of input is given 3 A positive integer n
、m
and k
, among n
(≤10000) It's the total number of hills ( So let's say that every mountain comes from 1 To n
Number ). Next m
That's ok , Each line gives 2 No more than one. n
The positive integer , Separate numbers with spaces , Each represents the number of two hills that can hear each other . It's guaranteed that each pair of hills is entered only once , There will be no duplicate relationship input . The last line gives k
(≤10) No more than one. n
The positive integer , Separate numbers with spaces , Represents the number of the mountain to be queried .
Output format :
In turn, for each queried hill in the input , The farthest mountain that can be reached by the chain transmission of the shout sent out in one line . Be careful : First of all, the output must be the one that can be sent by the query . If there is more than one mountain like this , Then output the one with the smallest number . If the outcry of this mountain can't reach any other mountain , The output 0.
sample input :
7 5 4
1 2
2 3
3 1
4 5
5 6
1 4 5 7
sample output :
2
6
4
0
边栏推荐
- Sublime text code formatting operation
- Spark的RDD(弹性分布式数据集)返回大结果集
- Codeforces Global Round 19
- Research Report on market supply and demand and strategy of double drum magnetic separator industry in China
- Research Report on market supply and demand and strategy of China's four flat leadless (QFN) packaging industry
- Chapter 6 datanode
- (lightoj - 1354) IP checking (Analog)
- 第6章 Rebalance详解
- Li Kou - 298th weekly match
- 第2章 HFDS的Shell操作
猜你喜欢
随机推荐
LeetCode1556. Thousand separated number
Remove the border when input is focused
LeetCode 1566. Repeat the pattern with length m at least k times
SQL quick start
300th weekly match - leetcode
新手必会的静态站点生成器——Gridsome
Market trend report, technical innovation and market forecast of China's desktop capacitance meter
China double brightening film (dbef) market trend report, technical dynamic innovation and market forecast
QT implementation window gradually disappears qpropertyanimation+ progress bar
LeetCode 1550. There are three consecutive arrays of odd numbers
力扣leetcode第 280 场周赛
Install Jupiter notebook under Anaconda
Acwing - game 55 of the week
(lightoj - 1349) Aladdin and the optimal invitation (greed)
解决Intel12代酷睿CPU单线程只给小核运行的问题
Codeforces Round #801 (Div. 2)A~C
Li Kou leetcode 280 weekly match
Chapter III principles of MapReduce framework
LeetCode 1640. Can I connect to form an array
Installation and use of VMware Tools and open VM tools: solve the problems of incomplete screen and unable to transfer files of virtual machines