In today's ABC305, I used multisource BFS to solve problem E. But it is giving TLE. Can anyone please point out the mistake? Moreover, an almost similar question also happened to appear in Codechef STARTERS 93. And an almost similar code, written by me, got accepted in it.

Problem Link: https://atcoder.jp/contests/abc305/tasks/abc305_e

Solution Link: https://atcoder.jp/contests/abc305/submissions/42175490

**Code**

Consider a simple linked list as an example: 1 — 2 — 3 — ... — n. Lets say, there is a security guard at each node, and the max_distance, the

ithguard can cover isi. If the indices of the guards are given in increasing order of the maximum distances they cover. You will push elements in the order: 1, 2, 3, ... n, in the queue.Then, for the ith node in the queue: you will be visiting all the nodes from (1, 2, ... i). Hence this is too slow and bound to give TLE.

Try to use multi-source dijkstra instead.

But why dijikstra what are we gonna minimise here , isnt we just need to minimise the stamina of guard at each level by 1 if possible

The main issue with the BFS approach is that you could be updating a node multiple times and in worst case, order of updates could be quadratic, as in the above (linked list) example.

Think of dijkstra as a way of picking the best node from those present in the queue (the one with the maximum remaining distance in our case), instead of just doing FCFS like BFS. It will ensure that when a node is selected from our queue it has the maximum remaining_distance this node will ever have, i.e., no other node will update the remaining_distance of the current node. This solves the time complexity issue. Read more about it in the proof here: link

You can implement dijkstra to maximize the remaining_distance of a node.

Thanks! I reviewed the proof and your example and understood the reason for TLE.

Just one more thing: according to proof of Dijkstra, why even do we ever need a queue? Can't we just use priority_queue in every question of BFS, 0-1 BFS, or Dijkstra? With just an extra logV complexity we can solve any question without worries of getting TLE.

Well, I don't really think I am smart enough to comment on an approach for all problems in general. Maybe some higher rated coder will respond to your query.

However, I think you shouldn't think so less of this extra logn. There are a lot of problems where an extra logn results in a TLE. For example if the expected time complexity of a question is O(nlogn), in most cases the constraints are such that O(nlog^2n) fails.

There could be a question where you have to perform a BFS inside a binary search. If you use dijkstra there, most likely your solution will TLE.