So, here's the problem that I've came up with:

Given a undirected weighted graph, consisting of n vertices and m edges. The task is to find all the edges that are a part of every shortest path from vertex 1 to vertex n. In another word, find all the edges that if we delete it from the original graph, the shortest path from vertex 1 to vertex n will change or there will be no path from vertex 1 to vertex n .

Constraint: n <= 3 x 10^5, m <= min(3e5, n * (n — 1) / 2)

Here's my observation to this problem:

1. First, we'll run Dijkstra in the original graph and find the shortest path from vertex 1 to vertex n. Let call it minimum_path.

2. Define the cost of each edge is a pair {0, original_weight}.

3. We'll run Dijkstra until the minimum cost it takes from vertex 1 to n is {x, minimum_path + y} (x and y are integer and y > 0). And after each time the function Dijkstra is called, we will trace all the edges on that shortest path and assign their value to {1, original_weight}. So the result is the value x in the last time y is equal to 0.

I think my solution is quite long and maybe incorrect, so I hope someone has a better solution to this problem.

Hi guys, so here's the thing:

I was so frustrated while submitting a solution to this problem : D. Reality Show, and constantly receiving a TLE verdict. I was pretty sure that the time complexity of my code was acceptable, so I decided to read the code from another. It turns out, my solution resembles their code, and after being confused for a while, I realized that they submitted it in C++ 20. After changing the language, my previous TLE code was accepted. I'm really confused right now; it's like there are some magic in C++ 20 or something.

Here is my submission:

225519286 (here's the C++ 17) 225519370 (here's the C++ 20)

Can anyone explain this to me? Thanks! :3