Hi All,

I was trying to solve this using Dijkstra.

I'm getting TLE in the last few test cases. Can someone suggest me any further optimizations I can make?

thanks! have a good day!

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

1 | Errichto | 206 |

2 | Monogon | 194 |

3 | SecondThread | 191 |

4 | pikmike | 187 |

4 | antontrygubO_o | 187 |

6 | vovuh | 185 |

7 | Ashishgup | 181 |

8 | Um_nik | 180 |

9 | Radewoosh | 169 |

10 | pashka | 167 |

Hi All,

I was trying to solve this using Dijkstra.

I'm getting TLE in the last few test cases. Can someone suggest me any further optimizations I can make?

thanks! have a good day!

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/20/2020 08:33:49 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

You can try adding the following line below #include <bits/stdc++.h>

## pragma GCC optimize("-Ofast")

exactly as it is.this should help

No proper question will use this

optimizationas a solution.i am just a beginner,i was just trying to help with the relatively little information i had that's all.

Ah, I see. However, this trick should only be used as a crutch when your solution barely doesn't pass the TL.

For practice sessions however, I would recommend avoiding this command, as it usually doesn't help you learn how to properly optimize your code

i understand, i only started CP a few weeks ago. so it's a pretty good opportunity to learn optimization techniques.

Your code actually runs in $$$O(\sum deg_i \cdot K_i)$$$. This is due to the

`addWaitingCost(node, time)`

code having $$$O(K_{node})$$$ complexity, and you calculate this value $$$O(deg_i)$$$ times for each vertex.An alternative idea will be to calculate

`addWaitingCost(node, time)`

when youreacha node and add the value to the current distance. This will be optimal as the faster you reach a node, the faster you can exit out of that node.Whilst this might seem slow at first, this will have an amortized complexity of $$$O(\sum K_i)$$$, since you compute the value only once for each vertex.

I would recommend reading the tutorial of the contest if you are stuck.

Thank you!

I'll have a look.

Even this approcah TLE'd on same testcase :(

Problem of modified code next: let's we can come to vertex $$$v$$$ at times $$$t_1 < t_2 < t_3 < \cdots < t_d$$$. Right code would process only pair ($$$v$$$, $$$t_1$$$) and skip all others. For that reason you have next line of code:

And it is correct line of code. Correct, but not in your case. That condition assumes that $$$dist[curNode] == t_1$$$, but later in dijkstra you update $$$dist[curNode]$$$:

And it breaks all! There could be test where $$$t_1 < t_2 < t_3 < \cdots < t_d < t_1 + waitingCost$$$. Because of that you'll actually process all pairs ($$$v$$$, $$$t_1$$$), ($$$v$$$, $$$t_2$$$), ($$$v$$$, $$$t_3$$$), ..., ($$$v$$$, $$$t_d$$$) — and it would be TL.

It could be easily fixed by updating $$$curDist$$$, not $$$dist[curNode]$$$:

Full AC version of code

P.S.

You had very strange output:

I think that this version a bit more convenient:

WoW. Correct!

Thanks for teaching this! Makes me realize how poorly I've understood and implemented Dijkstra's.

I'll revisit the topic and get back to you if I've any queries.

Thank you so much! :))

I solved this problem a few months ago, and used two binary searches.

Haven't read the editorial for this problem, but this is how I solved it, at least.

Thanks for your help!

I'll try this too! X)

Just use Dijkstra's algorithm to find shortest path from node 1 to any node and while on a node just wait till the current node is "OK" to go. You can simply find the first time after you reach it which is "OK" to go, just this can be done just by simply traversing the arrival list at that node.

See my implementation for more details:

Solution

PS:By "OK" I mean you can go from that node after all consecutive arrivals gone.

Sorry for my English.