M_sea

CF1106D Lunar New Year and a Wander
好好的一场rated的比赛怎么就unrated了呢qwq这样做是要向全世界人民谢罪的CodeForcesLuogu
扫描右侧二维码阅读全文
01
2019/02

CF1106D Lunar New Year and a Wander

好好的一场rated的比赛怎么就unrated了呢qwq

这样做是要向全世界人民谢罪的

CodeForces

Luogu

分析

Orz ych 秒了这题

然而我也一眼切了


很简单的一道题。

用小根堆来维护一下到达过的点能到达的所有点的编号。

每次取出堆顶,更新一下就行了。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

struct Edge { int v,nxt; };
Edge e[N<<1];
int head[N],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

priority_queue<int> Q;
int vis[N];

int main() {
    int n=read(),m=read(); n=n;
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    vis[1]=1; Q.push(-1);
    while (!Q.empty()) {
        int u=-Q.top(); Q.pop();
        printf("%d ",u);
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if (!vis[v]) Q.push(-v),vis[v]=1;
        }
    }
    return 0;
}
最后修改:2019 年 02 月 07 日 08 : 37 PM

7 条评论

  1. ttyclear

    您们太强辣!!!

    1. M_sea
      @ttyclear

      您太假啦!!!

  2. smy

    快发EF题解啊

    1. M_sea
      @smy

      放假了懒得写啊......

      然而我并没有看懂

      1. smy
        @M_sea

        催更EF题解qwq

        1. M_sea
          @smy

          E晚点再写,F看不懂啊qwq

      2. smy
        @M_sea

        F就是一堆数论板子啊

发表评论