Codeforces Problem - Dijkstra?

Problem link: Problem - C - Codeforces
My submission: Submission #73388695 - Codeforces

Why am I getting TLE?

The weight of an edge can be upto 10^6, and number of edges can be upto 10^5. The distance between two vertices isn’t necessarily going to fit in an integer. I tried changing the bounds in your code and it does get accepted. Go try long long :slight_smile:

Could you share the link to your submission please?

Here’s your updated solution: Submission #73396258 - Codeforces

Sorry for the mess, was feeling lazy so I just replaced every occurence of int with unsigned long long, and changed the INT_MAX to one for ULL (INTT_MAX) :stuck_out_tongue:

For reference, I just coded up an implementation too, to make sure that straightforward Dijkstra does actually work within limits. Here’s that submission: Submission #73394454 - Codeforces.

In my submission, I considered only the minimum weight edge between any pair of vertices, using a vector of maps for adjacency list. I don’t know if that gives any performance boost or just ends up being slower in the end, though.

1 Like