2025年喊山第二部_软组raid0

喊山，是人双手围在嘴边成喇叭状，对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递，回荡于深谷之间，传送到人们耳中，发出约定俗成的“讯号”，达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”，慢慢地人们在生活实践中发现了它的实用价值，便把它作为一种交流工具世代传袭使用。（图文摘自：http://news.xrxxw.com/newsshow-8018.html）

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

输入格式：
输入第一行给出3个正整数n、m和k，其中n（≤10000）是总的山头数（于是假设每个山头从1到n编号）。接下来的m行，每行给出2个不超过n的正整数，数字间用空格分开，分别代表可以听到彼此的两个山头的编号。这里保证每一对山头只被输入一次，不会有重复的关系输入。最后一行给出k（≤10）个不超过n的正整数，数字间用空格分开，代表需要查询的山头的编号。

输出格式：
依次对于输入中的每个被查询的山头，在一行中输出其发出的呼喊能够连锁传达到的最远的那个山头。注意：被输出的首先必须是被查询的个山头能连锁传到的。若这样的山头不只一个，则输出编号最小的那个。若此山头的呼喊无法传到任何其他山头，则输出0。

输入样例：

输出样例：

题解
堆优化版dijsktra

#include

#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 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,greater > 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<
    }

}

bfs版

#include

#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 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,greater > 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);

    queueq;

    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<
    }

}

2025年喊山第二部_软组raid0

相关推荐