Need help in the ARC 61 , question E
Link : E - Snuke's Subway Trip
Here how can I use either Dijkistra’s or more efficient 0-1 BFS , please help I don’t understand editorials (as they are in japanese)
I don’t understand japanse either but saw this 
I’m bussy now but in a few hours, If you haven’t solved it yet, I try
1 Like
I said it already , yes please try and explain.
The answer can be obtained by solving the shortest path problem with (current station, last used company) at the top.
In this solution, the number of vertices is at most O(M). Because it is the best to reach each station
The number of types of companies used later is the maximum number of lines departing from the station. Total this number The total at all stations is only a constant multiple of the number of lines.
However, if you do not set up the edges efficiently, the number of edges will be O(M2 ) And so on Execution will not end in time.
For example, the number of edges can be O(N + M) at most if you use the following method.
• In case of transferring to the route of the same company, the 0-length side is used for all routes. Stretch to the destination of
• As an alternative to the case of transferring to a route of a different company, the apex of (current station, −1) Stretch a zero-length side so that you can move to. (Image of going out from the ticket gate)
From the top of (current station, −1), set a length of 1 to the destination for all company routes (image of entering the ticket gate, new fee will be charged at this point).
• The start is the vertex of (1, −1). The goal is the vertex of (N, −1). After that, the Dijkstra method can be used to find the answer in a sufficiently short time.
This is a translation
Hope it helps
Currently involved in making/planning content for my YT channel, I’ll give it a try tonight 
Also you might enjoy my recent video on cses problem array desciptions: Dynamic Programming : Array Description - YouTube
2 Likes
Thanks for suggesting , I will try 
Isn’t it straight-forward?
When using deque for 0-1 BFS,
If the current edge belongs to Ci, and while checking all neighbours of the current node;
If the edge that leads to a new node belongs to the same Ci -> then push it forward with no additional cost.
else push it backwards with additional cost of 1.
I don’t think so , 
Okay let me implement and see to it.
Yeah u can try , I will implement it after implementing some other que.
Yes, this method is wrong.
Getting wrong answer in 11/63 cases.
Submission
If anyone can point out why its failing will be helpful to me. Thank you :))
You are not keeping track of the company you last used to arrive at the stored distance. Say, you arrived at some node with route owned by company A. Later, you found a smaller path for that station using company B. Since smaller paths are processed earlier, you’ll process the station and be done with it.
However, the arrival at the station (using a longer path) with route of company A is still sitting at the back of the queue. While processing it later, you incorrectly take the smallest path that you had achieved using company B and make further calculations using that distance.
This results in WA.
1 Like
after some failed attemps I could pass it with dijkistra. Try to understand the code I cannot include a full explanation right now. The main idea is that each state of the priority queue contains the lenght, the current station and the last company used. The key optimization was this: for each station just discriminate the companies that arrive more than once to that station, otherwise consider that the company number is -1.
So if i store that information and whenever new company route visits new node. I still process it. But I think it would lead to TLE.
If you count the pairs of relevant (city, company), it will be at max 2M. This is because there are M edges, and assuming that each edge belongs to a distinct company, it will result in creating a distinct node for 2 cities.
So that should not TLE, if you make the additional observation that you do not need to store the distance of all pairs of (city, company). If there’s a company such that there’s only one edge adjacent to a city, we know that choosing it will always result in a +1 weight. So we make an extra node for each city that holds the shortest distance data for such once-appearing companies in that city. Mark this node as (city, -1). This is exactly what @carre mentions in his answer, and you can view his submission.
2 Likes