We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The final test case has 2500 nodes and over 3 million edges (almost all duplicates), and is quite strict about timing out. Using C# with a heap-based Dijkstra algorithm, Dijkstra's took about 10ms while the input-parsing took 2 seconds. Just the Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse) alone for the edges was enough to time it out. about 10-20% of that is the readline itself, and the rest is from parsing strings into ints.
Ultimately this seems to be an exercise in optimizing IO rather than a graph algorithm.
Edit: I played around with it and found a simpler way to improve parse run-time for C#. Create a dictionary that maps vertex strings to the corresponding parsed integer. i.e.
var parse = new Dictionary<string, int>();
for (int i = 1; i <= n; i++){
parse[i.ToString()] = i;
}
Where n is the number of vertices as given in the problem. Then you can use parse[a] instead of int.Parse(a) for the vertices in each edge when you read them. Still have to use int.Parse for weights, since those can be very large. (I guess you could extend the dictionary up to 100000 (upper limit of weight) but that's a bit obscene). I found that this was sufficiently faster to avoid timing out.
Edit #2: An even simpler way to is to write your own string to int parser, as stevelang pointed out in a response to this post. The built-in one in C# is notoriously slow. This has the advantage of also working for edges.
Dijkstra: Shortest Reach 2
You are viewing a single comment's thread. Return to all comments →
The final test case has 2500 nodes and over 3 million edges (almost all duplicates), and is quite strict about timing out. Using C# with a heap-based Dijkstra algorithm, Dijkstra's took about 10ms while the input-parsing took 2 seconds. Just the Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse) alone for the edges was enough to time it out. about 10-20% of that is the readline itself, and the rest is from parsing strings into ints.
Ultimately this seems to be an exercise in optimizing IO rather than a graph algorithm.
Edit: I played around with it and found a simpler way to improve parse run-time for C#. Create a dictionary that maps vertex strings to the corresponding parsed integer. i.e.
Where n is the number of vertices as given in the problem. Then you can use parse[a] instead of int.Parse(a) for the vertices in each edge when you read them. Still have to use int.Parse for weights, since those can be very large. (I guess you could extend the dictionary up to 100000 (upper limit of weight) but that's a bit obscene). I found that this was sufficiently faster to avoid timing out.
Edit #2: An even simpler way to is to write your own string to int parser, as stevelang pointed out in a response to this post. The built-in one in C# is notoriously slow. This has the advantage of also working for edges.