Commuter Pass

So I’m doing this problem, and I can’t seem to figure out how to calculate the cost of a path. I can easily tell if a single point or edge is on a shortest path for the commuter pass, but I can’t tell if a series of paths are, resulting in an incorrect output.

Could anyone help?

Nice problem. Notice that the path from U to V should optimally intersect with the path S to T one time (if you have a solution that intersects more than once, you can convert to one of shorter length that intersects just once).

Then think about how to efficiently try the intersection points in linear time. May involve some precomputation.

I think that would require trying pairs of points- One part from U, and another from V. This would require quadratic time in and of itself, but I’d also have to check if those 2 points are on a shortest path, which would require some sort of all-pairs shortest path, wouldn’t it?

Thought of an easier solution: optimal path will either use 0-cost edges from a path from S to T (in the same direction) or edges from T to S (in the same direction). So your original solution is almost correct, just need two passes with directed edges.

What I was initially thinking is similar to the usaco.guide’s solution with dynamic programming. Needs dynamic programming to match up all pairs (X,Y) of entry/exit points in linear time instead of quadratic.

Why would the optimal path only use 0-cost edges in a single direction?

The issue with your original idea is that using undirected 0 cost edges from any shortest path from S to T allows you to use edges from more than one path to get from U to V. Well, how can you fix that problem? Just limit yourself to using edges in one direction. Then you have to try both S->T and T->S. These edges form a DAG (directed acyclic graph).

Yeah… but like why would using edges in one direction fix that problem?

Also, for some reason this code here doesn’t work- it TLEs and even spits out a runtime error and I can’t figure out why for the life of me.

EDIT: fixed it now, but now it WAs.

So I looked a bit at the solution, and they said that it’s possible to keep track of all the shortest paths by recording the “parent” of each node. But this is a DAG, not a tree, so I’m not sure how to keep track of it.

You’re right, my simpler solution actually fails on some edge cases.

Right, for each exit point Y consider all possible previous entry points X by running a dynamic programming that merges dist[U] with the min function down the “shortest path DAG” from S to T. There are a couple good solutions on usaco.guide.

You still have to consider both directions, either paths from S to T or T to S.

What are these entry and exit points?

The path U->V enters a path S->T at some point X and exits at some point Y. It’s optimal to only have one such intersection.

C++ solution: https://ideone.com/tCpCIA

Yeah, I managed to solve it myself after looking at the solution a bit.

Might as well post my code here: Paste ofCode

Could anyone help me with this problem? My code: https://oj.uz/submission/380285
Im only getting 15 points, and I think im doing what both of you did. I dont know whether I have a bug or my implementation is incorrect

Your typedefs are confusing, don’t use variable names that look the same: “pi” vs “pl” or “int” and “tint”. At least one of the bugs is in Dijkstra’s: you need long distances in the priority queue.

You also don’t need another DFS to find the topological order, you can produce the order with Dijkstra’s on S.

I’m also not sure if lines 133/134 are correct or necessary.