团体程序设计天梯赛-练习集 - L3-008 喊山（30 分）

#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
intn,m,k;
intvis[10009], lvl[10009], book[10009];
vector<int>vec[10009];
intbfs(ints)
{
intma=0, idx=-1;
mem(lvl,0), mem(book,0);
queue<int>q;
q.push(s);
lvl[s]=0;
book[s]=1;
inttp,v;
while(!q.empty())
    {
tp=q.front(), q.pop();
for(inti=0;i<vec[tp].size();i++)
        {
v=vec[tp][i];
if(!book[v])
            {
book[v]=1;
lvl[v]=lvl[tp]+1;
q.push(v);
if(lvl[v]>ma) ma=lvl[v], idx=v;
elseif(lvl[v]==ma&&idx>v) idx=v;
            }
        }
    }
returnidx;
}
intmain()
{
intu,v;
scanf("%d%d%d",&n,&m,&k);
for(inti=0;i<m;i++)
    {
scanf("%d%d",&u,&v);
vec[u].push_back(v);
vec[v].push_back(u);
vis[u]=vis[v]=1;
    }
while(k--)
    {
scanf("%d",&u);
if(!vis[u]) puts("0");
elseprintf("%d\n",bfs(u));
    }
return0;
}

#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
constintmaxn=1e4+10;
intn,m,k;
intdis[maxn], vis[maxn], book[maxn];
unordered_map<int,int>ump;
intfhash(inta,intb)
{
returna*10000+b;
}
intdijkstra(ints)
{
intw, ma=-1, idx=-1;
dis[s]=0;
while(1)
    {
intmi=INF; s=-1;
for(inti=1;i<=n;i++)
if(!vis[i] &&mi>dis[i]) mi=dis[i], s=i;
if(s==-1) returnidx;
vis[s]=1;
for(inti=1;i<=n;i++)
        {
w=ump[fhash(s,i)]==1?1:INF;
if(!vis[i] &&mi+w<dis[i])
            {
dis[i]=mi+w;
if(ma<dis[i]) ma=dis[i], idx=i;
elseif(ma==dis[i] &&i<idx) idx=i;
            }
        }
    }
}
intmain()
{
intu,v,w;
scanf("%d%d%d",&n,&m,&k);
for(inti=0;i<m;i++)
    {
scanf("%d%d",&u,&v);
ump[fhash(u,v)]=ump[fhash(v,u)]=1;
book[u]=book[v]=1;
    }
while(k--)
    {
scanf("%d",&u);
if(!book[u]) puts("0");
else        {
mem(dis,INF), mem(vis,0);
intidx=dijkstra(u);
printf("%d\n",idx);
        }
    }
return0;
}