Hello codeforces, I was solving [this](https://codeforces.com/problemset/problem/986/A) problem and I ended up with below solution, but this solution doesn't seem to work on **test case 5**, can you help me find where I've gone wrong and I don't want to see the editorial until I don't get my approach accepted. It's a simple bfs if you've got time to see it. Please help..I wasted so much time on this.↵
↵
**Mysolution↵
approach:** Firstly, I am making a bfs call from every node from 1 to n and finding their neighbours or second-neighbours and so on..so that minimum s towns having a different type of goods and for finding cost I am using a level array. Suppose I am starting bfs from node-2 then level of this node I am taking 0 and its neighbours level 1 and so on, so it gives me nearest s towns who has to produce a different type of goods and for answer, I am summing their cost. Hope you understood my approach.↵
↵
Code↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define N 100005↵
#define mod 1000000007↵
↵
vector<int> adj[N];↵
vector<bool> visited(N, false);↵
unordered_map<int, int> mp;↵
vector<int> goods(N);↵
vector<int> level(N, 0);↵
int ans=0;↵
int n, m, k, s;↵
↵
void bfs(int node)↵
{↵
level[node]=0;↵
queue<int> q;↵
mp[goods[node]]++;↵
q.push(node);↵
while(!q.empty())↵
{↵
int tp=q.front();↵
q.pop();↵
visited[tp]=true;↵
if(mp.find(goods[tp])==mp.end())↵
{↵
ans+=level[tp];↵
mp[goods[tp]]++;↵
}↵
cout<<ans<<endl;↵
if(mp.size()==s)↵
{↵
cout<<ans<<" ";↵
return;↵
}↵
for(auto child: adj[tp])↵
{↵
if(!visited[child])↵
{↵
q.push(child);↵
level[child]=level[tp]+1;↵
}↵
}↵
}↵
}↵
↵
void solve()↵
{↵
cin>>n>>m>>k>>s;↵
rep(i, n)↵
{↵
cin>>goods[i];↵
}↵
rep(i, m)↵
{↵
int u, v;↵
cin>>u>>v;↵
u--, v--;↵
adj[u].push_back(v);↵
adj[v].push_back(u);↵
}↵
for(int i=0;i<n;i++)↵
{↵
ans=0;↵
mp.clear();↵
visited.clear();↵
visited=vector<bool>(N, false);↵
bfs(i);↵
}↵
↵
}↵
↵
signed main() {↵
// int t;cin>>t;while(t--)↵
solve();↵
↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
**My
↵
Code↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define N 100005↵
#define mod 1000000007↵
↵
vector<int> adj[N];↵
vector<bool> visited(N, false);↵
unordered_map<int, int> mp;↵
vector<int> goods(N);↵
vector<int> level(N, 0);↵
int ans=0;↵
int n, m, k, s;↵
↵
void bfs(int node)↵
{↵
level[node]=0;↵
queue<int> q;↵
mp[goods[node]]++;↵
q.push(node);↵
while(!q.empty())↵
{↵
int tp=q.front();↵
q.pop();↵
visited[tp]=true;↵
if(mp.find(goods[tp])==mp.end())↵
{↵
ans+=level[tp];↵
mp[goods[tp]]++;↵
}↵
cout<<ans<<endl;↵
if(mp.size()==s)↵
{↵
cout<<ans<<" ";↵
return;↵
}↵
for(auto child: adj[tp])↵
{↵
if(!visited[child])↵
{↵
q.push(child);↵
level[child]=level[tp]+1;↵
}↵
}↵
}↵
}↵
↵
void solve()↵
{↵
cin>>n>>m>>k>>s;↵
rep(i, n)↵
{↵
cin>>goods[i];↵
}↵
rep(i, m)↵
{↵
int u, v;↵
cin>>u>>v;↵
u--, v--;↵
adj[u].push_back(v);↵
adj[v].push_back(u);↵
}↵
for(int i=0;i<n;i++)↵
{↵
ans=0;↵
mp.clear();↵
visited.clear();↵
visited=vector<bool>(N, false);↵
bfs(i);↵
}↵
↵
}↵
↵
signed main() {↵
// int t;cin>>t;while(t--)↵
solve();↵
↵
↵
return 0;↵
}↵
~~~~~↵
↵
