[BZOJ] 3402: [Usaco 2009 오픈] 숨바꼭질 (spfa)

http://www.lydsy.com/JudgeOnline/problem.php?id=3402
또 spfa 문제.

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

  

const int N=20005, Q=N*10, oo=~0u>>2;

int q[Q], front, tail, d[N], vis[N], ihead[N], cnt, n, m;

struct ED { int to, next; }e[Q];

void add(int u, int v) {

    e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v;

    e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].to=u;

}

void spfa() {

    q[tail++]=1;

    for1(i, 2, n) d[i]=oo;

    vis[1]=1;

    while(front!=tail) {

        int v, u=q[front++]; if(front==Q) front=0; vis[u]=0;

        for(int i=ihead[u]; i; i=e[i].next) if(d[v=e[i].to]>d[u]+1) {

            d[v]=d[u]+1;

            if(!vis[v]) {

                vis[v]=1;

                q[tail++]=v; if(tail==Q) tail=0;

            }

        }

    }

}

  

int main() {

    read(n); read(m);

    for1(i, 1, m) {

        int u=getint(), v=getint();

        add(u, v);

    }

    spfa();

    int mx=0, ans=0, id=oo;

    for1(i, 1, n) mx=max(d[i], mx);

    for1(i, 1, n) if(d[i]==mx) { ++ans; id=min(i, id); }

    printf("%d %d %d", id, mx, ans);

    return 0;

}

 
 
 
 
Description
    베 시 는 존 과 숨바꼭질 놀 이 를 하고 있 었 다.
    그녀 는 그녀 가 숨 을 수 있 는 안전 한 외양간 을 모두 찾 으 려 고 한다. 모두 N (2 ≤ N ≤ 20000) 개의 외양간 이 있 고 1 ~ N 호 로 편성 되 었 다. 그녀 는 존 (소 잡 는 자) 이 외양간 1 에서 출발 하 는 것 을 알 고 있다. 모든 외양간 은 M (1 ≤ M ≤ 50000) 개의 양 방향 도로 로 연결 되 어 있다.각 양 방향 길 은 두 개의 서로 다른 외양간 을 연결 합 니 다. 모든 외양간 은 서로 통 합 됩 니 다. 베 시 는 외양간 과 가장 멀리 떨 어 진 외양간 이 안전 하 다 고 생각 합 니 다. 두 외양간 의 거 리 는 한 외양간 에서 다른 외양간 까지 최소한 통과 해 야 할 도로 수 를 말 합 니 다. 베 시 를 도와 안전 한 외양간 을 찾 아 주세요.
Input
    첫 번 째 줄 은 두 개의 정수 N 과 M 을 입력 한 후에 M 줄 은 한 줄 에 두 개의 정 수 를 입력 하여 한 길의 두 점 을 나타 낸다.
   
Output
 한 줄 에 만 세 개의 정 수 를 출력 합 니 다. 첫 번 째 는 안전 한 외양간 (여러 개 있 으 면 출력 번호 가 가장 작은 것) 을 표시 합 니 다.두 번 째 는 외양간 1 과 안전 한 외양간 의 거 리 를 나타 낸다.세 번 째 는 몇 개의 안전 한 외양간 이 있 는 지 를 나타 낸다.
Sample Input
6 7
3 6
4 3
3 2
1 3
1 2
2 4
5 2
Sample Output
4 2 3
HINT
Source
Silver