Can any one explain the topic and also tell me the list of some good problems.Thanks in advance.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
https://codeforces.me/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 nodeX
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 fromX
to the real source at the beginning of each path.Wow!
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.