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

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

1 | tourist | 3803 |

2 | Benq | 3783 |

3 | Radewoosh | 3602 |

4 | Um_nik | 3541 |

5 | fantasy | 3526 |

6 | maroonrk | 3504 |

7 | ko_osaga | 3500 |

8 | jiangly | 3465 |

9 | orzdevinwang | 3460 |

10 | cnnfls_csy | 3427 |

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

1 | awoo | 180 |

2 | -is-this-fft- | 178 |

3 | nor | 169 |

4 | Um_nik | 168 |

5 | SecondThread | 164 |

6 | maroonrk | 163 |

6 | adamant | 163 |

8 | kostka | 161 |

9 | YouKn0wWho | 158 |

10 | antontrygubO_o | 154 |

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/30/2023 14:39:20 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

how we can do if the number of nodes and edges are more than 2e5

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.

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.

Another Problem: 986A - Fair

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

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

A nice leetcode problem on multisource bfs: https://leetcode.com/problems/rotting-oranges/

This is a nice problem illustrating the use of multiple source BFS: Monsters

Multi source bfs is that queue initially contains multiple nodes instead of just node and then do just bfs.