Can any one explain the topic and also tell me the list of some good problems.Thanks in advance.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 159 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
| Название |
|---|



https://mirror.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,Care your multiple sources. We can create an additional nodeXand 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 fromXto the real source at the beginning of each path.Wow!
great thought !!
Thank you :)
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.
This is a nice problem illustrating the use of multiple source BFS: Monsters
You should do "monsters" problem on cses.
A little addition over multi-source bfs
thanks, this one is quite intuitive through multi-source bfs