Niflheimr is playing Minecraft recently. He occupies a lot of towns, and there are many diamonds inside some of those towns.
Whenever he runs out of diamond, he has to figure out the nearest town with diamonds from his current location.
Doing this task every time waste a lot of time. He asks you to help him for the calculation. For every town, find the shortest distance to get diamonds from a nearby town which has diamonds. If the town itself has diamonds, the distance would be 0.
Hint: Use BFS (Breadth First Search) and std::queue.
You are provided with the following code:
#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
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!
// Output
for (int i = 1; i <= N; i++) {
cout << Dist[i] << '\n';
}
return 0;
}
You may take it as reference. You are not required to use this code, though.
First line of input contains three integer N, M, K, denoting the number of towns, the amount of roads between towns and the number of towns which has diamond.
All the towns are numbered from 1 to N.
For the next M lines, each of them contains two integer a, b, meaning there is a road between a and b. All the roads are bidirectional, and the length of these roads are all 1.
The last line of input contains K distinct integers, denoting the towns which has diamonds.
It is guaranteed that:
Output consists of N lines.
For i-th line, output the shortest distance Niflheimr has to travel from town i to get a diamond.