Can any one explain the topic and also tell me the list of some good problems.Thanks in advance.

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

1 | tourist | 3805 |

2 | maroonrk | 3637 |

3 | Benq | 3513 |

4 | ecnerwala | 3506 |

5 | MiracleFaFa | 3466 |

6 | slime | 3428 |

7 | jiangly | 3415 |

8 | Radewoosh | 3399 |

9 | greenheadstrange | 3393 |

10 | djq_cpp | 3391 |

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

1 | awoo | 192 |

2 | -is-this-fft- | 191 |

3 | Monogon | 185 |

4 | Um_nik | 182 |

4 | YouKn0wWho | 182 |

6 | maroonrk | 170 |

7 | antontrygubO_o | 167 |

8 | errorgorn | 166 |

8 | kostka | 166 |

10 | SecondThread | 165 |

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/17/2022 10:57:48 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

https://www.codechef.com/SNCKPB17/problems/SNSOCIAL/

Concept : You push all the cells/nodes/vertices which are the so called "Source" / Starting Vertices in a queue. In these types of problems you generally have to find the shortest Distance/Cost of reaching all the vertices.

After pushing all the source vertices into the queue(priority queue/set) and performing the usual Djikstra you get your desired answer.

This works in the usual time limit if the total number of nodes and edges are not more than say ~2e5

thanks...sir

Good beginner level problem related to this topic- http://www.spoj.com/problems/BITMAP/

http://codeforces.com/contest/1283/problem/D

https://codeforces.com/contest/1272/problem/E

Another way to think about multiple sources that's potentially nicer to code is to add a fake source with edges to all the real sources, then BFS as normal, then subtract 1 from all the distances.

Thanks for the implementation trick!!!

can you please elaborate what are you trying to tell ?

Imagine this is your original graph (not including the red node/edges), and

`A`

,`B`

,`C`

are your multiple sources. We can create an additional node`X`

and the red edges shown, then do a standard BFS starting from X. Finally, all the distances will be 1 more than they should be, because you had the extra hop from`X`

to the real source at the beginning of each path.Sir, how does it affects the time complexity? does it make any difference at all.

I think there should be no huge differences. As our red coder said above, it's just nicer to code, as traditionally, you start with a single vertex only.

If I misunderstand anything, please tell me.

Yes, I also see that it doesn't affect the time complexity to a great extent.

Another Problem: 986A - Fair

Add all the nodes you want to BFS from into the initial queue and run it.

Here is another one!

https://usaco.guide/gold/bfs

Theory + 11 questions to practice from various OJs

https://www.spoj.com/problems/AKBAR/

I love this community. Thanks for various approaches on multi source BFS.