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 
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) 
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