ParagonX97's blog

A Shortest Path Problem
By ParagonX97, history, 6 years ago, In English

Hi Codeforces!!

I have tried this problem using Dijkstra, but it is giving me TLE :(, do you know a faster way to do it?

Thanks in advance!!! :)

-Problem Description-

You are given an undirected graph with weighted edges. You have to find the minimum length of path between vertex 0 and vertex n − 1 and the number of those paths with minimum length.

-Input-

There are many several test cases. Each test case begins with two positive integers n and m (2 ≤ n ≤ 100000, n − 1 ≤ m ≤ 100000) — the number of vertices and the number of edges in the graph. Each of the following m lines describes a corresponding edge. Each one contains three integers u, v and c (0 ≤ u, v < n, 1 ≤ c ≤ 1000) — these numbers denote an edge that connects vertices u and v and has weight c. The graph may contain multiple edges between the same pair of vertices and loops. It is guaranteed that the graph is connected.

-Output-

For each test case print one line with two numbers separated by a space, the minimum length of path between vertices 0 and n−1, and the number of paths between vertices 0 and n−1 with minimum length modulo 10^9 + 7.

-Sample Input-

5 12 4 3 3 3 2 1 0 2 2 2 0 2 0 1 4 4 1 2 4 1 5 0 1 2 3 1 1 3 3 1 2 1 1 0 3 1

-Sample Output-

4 3

Here is my code: https://ide.geeksforgeeks.org/gEDklVLLAF

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Try dynamic programming,your current algorithm is like backtracking for all the solutions,resulting an exponential time.Let be the distance between 0 and vertex x be d[x].Looking at the Dijkstra algorithm,if you'll keep only the edges which are contained in at least one minimum path(it is not hard to find them based on the array d,knowing all the edge weights), you will have all the paths on a graph only with those edges.Also,let's direct each of this edges (denote them {a,b})- the edge from a to b if d[a]<d[b] and from b to a if d[b]<d[b] (they can't be equal,since all costs are >=1).Now you got a directed acyclic graph and the problem reduces to counting the number of paths from 0 to n-1 in it.Hint:process the in the topologic order,then think from where you can come to a node in a path from 0.The complexity is O(mlogn) from the Dijkstra algorithm.The recurrence could be applied directly during the Dijkstra algorithm,but I found it a bit simpler to explain this way.Also,I find it a bit strange that the shortest path must be modulo 10^9+7,not the number of paths, because the number of paths may not fit long long.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Accepted!! :)

    Yes, I had read it a little bit wrong, you have to apply modulo to the number of paths, not to the distance

    Thanks Bodo!!! :)

    → Reply