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

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

1 | tourist | 3565 |

2 | Benq | 3540 |

3 | Petr | 3519 |

4 | maroonrk | 3503 |

5 | jiangly | 3391 |

6 | ecnerwala | 3363 |

7 | Radewoosh | 3349 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

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

1 | 1-gon | 199 |

2 | Errichto | 196 |

3 | rng_58 | 194 |

4 | SecondThread | 186 |

4 | awoo | 186 |

6 | Um_nik | 182 |

7 | vovuh | 178 |

8 | Ashishgup | 176 |

9 | antontrygubO_o | 174 |

10 | -is-this-fft- | 173 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/05/2021 07:01:47 (i2).

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 - Ярмарка

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/