# | User | Rating |
---|---|---|

1 | tourist | 3870 |

2 | Benq | 3618 |

3 | Miracle03 | 3453 |

4 | peehs_moorhsum | 3430 |

5 | Radewoosh | 3418 |

6 | Petr | 3408 |

7 | maroonrk | 3387 |

8 | sunset | 3338 |

9 | ko_osaga | 3334 |

9 | jiangly | 3334 |

# | User | Contrib. |
---|---|---|

1 | YouKn0wWho | 214 |

2 | 1-gon | 203 |

3 | Um_nik | 195 |

4 | Errichto | 181 |

5 | awoo | 180 |

6 | tourist | 176 |

7 | sus | 175 |

8 | antontrygubO_o | 173 |

9 | maroonrk | 170 |

10 | SecondThread | 169 |

Hello codeforces, I was solving this 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.

**My 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;
}
```

**But** not solving problems, seeing Recent actions, standings, tourist's rating and other top coders most of the time. Someone would say, "It's rediculous", but I do. Any suggestions?

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/09/2021 14:27:29 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|