Out of the Abyss Solution

 

Problem

###Statement:

In a far away Galaxy of Tilky Way, there was a planet Tarth where the sport of Tompetitive Toding was very popular. According to legends, there lived a setter who loved giving optimized Dijkstra and Floyd Warshall algorithms in TCDSAP exams.

Commander Tresdin, having obtained stones, must hurry out of the abyss to save Stonehall! The abyss can be represented as an unweighted graph $G$ containing $N$ nodes and $M$ edges. The abyss is chaotic, and hence $G$ can be disconnected as well. $K$ out of these $N$ nodes are special nodes which have a portal to escape from the abyss.

Commander Tresdin met Rubik, the Grand Mage, who offered to help teleport her to the nearest portal. But for that, he needs to know the distance to the nearest portal (that is, the minimum number of edges that have to be traversed)! Hence, given $Q$ queries, each giving a node $u$, i.e. the Node where Commander Tresdin and Rubik are, print the distance to reach the nearest special node. Print $-1$ if its not possible to reach a special node from their starting point.

$''We \ shall \ meet \ again \ after \ your \ conquest \ against \ the \ abyssal \ fire.''$ $-Rubik$

###Input:

• The first line contains $T -$ Number of test cases in a file.
• The first line of each test case has $3$ integers, $N$, $M$ and $K$, denoting number of nodes, number of edges, and number of special nodes respectively.
• Next $M$ lines have $2$ integers each - $u$ $v$ - denoting that there is an (undirected) edge between $u$ and $v$.
• Next line has $K$ space separated integers denoting the special nodes.
• Next line has a single integer $Q$ - the number of queries.
• Next $Q$ lines contain $1$ integer each - $u$ - the starting node for Commander Tresdin.

###Output:

For every query, $-1$ if its not possible to reach any special node by travelling along the given edges starting from node $u$. Else, print the distance to the nearest special node.

###Constraints

• $1 \leq T \leq 1000$
• $1 \leq N,Q,K \leq 10^5$
• $1 \leq u,v \leq N$
• $1 \leq M \leq 2.5*10^5$
• Sum of $N$ over all $T$ is $\leq 10^6$
• Sum of $Q$ over all $T$ is $\leq 10^6$
• Sum of $M$ over all $T$ is $\leq 2.5*10^6$
• $G$ does not have self loops or multiple edges.

###Subtasks

• 20% points - $N,Q \leq 100, M \leq 200$.
• 80% points - Original Constraints

###Sample Input:

1
5 3 3
1 2
1 3
2 3
1 3 5
5
1
2
3
4
5

###Sample Output:

0
1
0
-1
0

###EXPLANATION:

• Nodes $1$, $3$ and $5$ themselves are special nodes and hence the minimum distance to a special node is $0$ (i.e. as Commander Tresdin already starts at a special node, she needs not travel any further to reach one).
• From Node $2$, we can travel an edge to reach Node $1$ or Node $3$, both at distance of $1$.
• Node $4$ is disconnected from all special nodes.. Starting from Node $4$, we cannot reach any special node. Hence $-1$ is printed.

Program :

#include<bits/stdc++.h>

#define int long long

#define pb push_back

#define endl '\n'

#define ff first

#define ss second

#define vi vector<int>

#define pii pair<int, int>

#define all(x) (x).begin(), (x).end()

#define rep(i, a, b) for(int i=a; i<b; i++)

#define setbits(x) __builtin_popcountll(x)

#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define INF 1e18

#define MAX 100005

#define mod 1000000007 // 1e9+7

#define watch(x) cout<<(#x)<<"="<<(x)<<"\n"

#define watch2(x,y) cout<<(#x)<<"="<<(x)<<" and "<<(#y)<< "=" <<(y)<<"\n"

using namespace std;

void hint() {

int n, m, k;

cin >> n >> m >> k;

vector<vector<int>> v(n + 1);

map<int, int> isSpl;

for (int i = 0; i < m; i++) {

int x, y;

cin >> x >> y;

v[x].pb(y);

v[y].pb(x);

}

queue<int> q;

bool vis[n + 1] = {0};

int dist[n + 1] = {0};

for (int i = 0; i < k; i++) {

int x; cin >> x;

isSpl[x] = 1;

q.push(x);

vis[x] = 1;

}

while (q.size()) {

int f = q.front();

q.pop();

// cout << f << endl;

for (auto x : v[f]) {

if (!vis[x]) {

vis[x] = 1;

q.push(x);

// cout << x << " " << dist[f] + 1 << endl;

dist[x] = dist[f] + 1;

}

}

}

// cout << endl;

// for (int i = 1; i <= n; i++) {

// cout << dist[i] << endl;

// }

// cout << endl;

int queries;

cin >> queries;

while (queries--) {

int x;

cin >> x;

if (isSpl[x]) {

cout << 0 << endl;

} else {

if (dist[x] == 0) {

cout << "-1" << endl;

} else {

cout << dist[x] << endl;

}

}

}

}

signed main() {

#ifndef ONLINE_JUDGE

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);

#endif

FIO

int t; cin >> t;

while (t--) {

hint();

}

}