# 11945 - Treasure Hunting
>author: Utin
###### tags: `BFS`

---

## Brief
See the code below

## Solution 0

#include <bits/stdc++.h>
using namespace std;

// G[i] is the neighbor towns of town i
vector<int> diamondTowns;
vector<int> G[100005];
int Dist[100005];

struct node {
    int id;
    int dist;
    node(int id, int l) {
        this->id = id;
        this->dist = l;
    }
};

int main() 
    int N, M, K;
    cin >> N >> M >> K;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for (int i = 0; i < K; i++) {
        int x;
        cin >> x;
        diamondTowns.push_back(x);
    }
    fill(Dist, Dist+100005, -1);

    queue<node> Q;

    // [TODO] complete the task!

    for (auto start : diamondTowns) {

        // for every diamond town the distance is 0
        Dist[start] = 0;
        Q.push(node(start, 0));

        while (Q.size()) {
            for (auto curr_town : G[Q.front().id]) {
                // the following method can ensure 
                // that every node will be traversed less than once
                if (Dist[curr_town] == -1 || Dist[curr_town] > Q.front().dist + 1) {
                    Dist[curr_town] = Q.front().dist + 1;
                    Q.push(node(curr_town, Q.front().dist + 1));
                }
            }
            Q.pop();
        }
    }

    // Output
    for (int i = 1; i <= N; i++) {
        cout << Dist[i] << '\n';
    }
    return 0;
}

// By Utin

## Solution 1

#include <bits/stdc++.h>
using namespace std;

// G[i] is the neighbor towns of town i
vector<int> diamondTowns;
vector<int> G[100005];
int Dist[100005];
bool color[100005];

struct node {
    int id;
    int dist;
    node(int id, int l) {
        this->id = id;
        this->dist = l;
    }
};

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for (int i = 0; i < K; i++) {
        int x;
        cin >> x;
        diamondTowns.push_back(x);
    }
    fill(Dist, Dist+100005, -1);

    queue<node> Q;

    // [TODO] complete the task!

    for (int i = 0; i < diamondTowns.size(); i++) {

        // initialize the color
        memset(color, 0, sizeof(color));

        // for every diamond town the distance is 0
        Dist[diamondTowns[i]] = 0;
        Q.push(node(diamondTowns[i], 0));
        color[Q.front().id] = true;

        while (Q.size()) {
            for (int j = 0; j < G[Q.front().id].size(); j++) {

                // treversal the new node
                if (!color[G[Q.front().id][j]]) {

                    // paint the node
                    color[G[Q.front().id][j]] = true;

                    // consider if it is necessary to go through the next node
                    if (Dist[G[Q.front().id][j]] == -1 || Dist[G[Q.front().id][j]] > Q.front().dist + 1) {
                        Dist[G[Q.front().id][j]] = Q.front().dist + 1;
                        Q.push(node(G[Q.front().id][j], Q.front().dist + 1));
                    }
                }
            }
            Q.pop();
        }
    }

    // Output
    for (int i = 1; i <= N; i++) {
        cout << Dist[i] << '\n';
    }
    return 0;
}

// By Utin

## Reference