I am trying to solve this problem for a while now but I can't come up with solution better than SPFA from every node which (for sure) gives TLE. so can you help finding a faster solution? thanks in advance.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
I am trying to solve this problem for a while now but I can't come up with solution better than SPFA from every node which (for sure) gives TLE. so can you help finding a faster solution? thanks in advance.
Name |
---|
Bellman-Ford?
SPFA is faster than Bellman-ford and it gives TLE :(
actually SPFA is an improvement of the Bellman–Ford algorithm
Oh, I see. I think I read the problem wrong.
Another idea: Assuming d[u][v] <= d[u][w] + d[w][v] holds, we can simply do a Bellman-Ford (or SPFA if you want) from vertex 1 to all other vertices in O(nm) and find pairs of distances in O(n^2) since we can rearrange the inequality to be d[w][v] >= d[u][v] — d[u][w], therefore all of the answers we gathered are valid. I'm guessing the condition still holds under negative edge weights as well, after you've removed the possibility of a negative cycle.
I'm sorry but I can't get your idea well.How doing Bellman-ford only from vertex 1 will guarantee finding the answer.
The answer is not going to be <insert shortest paths algorithm here>, that would be boring.
Maybe this gives TLE but here is what I would do. First, let's check if there is a negative cycle. If so, output
-inf
. Now, letdp[u]
denote the length of the shortest path that ends with the vertexu
. To calculatedp[u]
we do this:Now, output the minimum of
dp[u]
over all verticesu
.thanks this is very nice approach actually. I think you may want to add
dp[v] = min(dp[v], cost(u, v))
first. any way I got the idea thanks alot.