JOI Commuter Pass DP Transition

Problems and Contests
#1

In this problem’s full solution, the USACO Guide uses DAG with transition state:

if (min(du[node], dp[0][par]) + min(dv[node], dp[1][par]) <=
			    dp[0][node] + dp[1][node]) {
				dp[0][node] = min(du[node], dp[0][par]);
				dp[1][node] = min(dv[node], dp[1][par]);
			}

when there are multiple parents that can reach on the DAG. Why is comparing the sum of the dpU and dpV optimal? What if one parent has {dpU, dpV} = {2,2} and another has {1,4}. Here, the algorithm would pick {2,2} because the sum is less.

If some descendent of our node in the DAG has {10,1} , then choosing the {1,4} would have given us {1,1} with sum = 2 instead of {2,1}. How does the algorithm handle this case? My guess was that by running the DP from s ->t and t->s, but when I kept on s->t, it still passed.

1 Like
#2

That’s a good question … it’s entirely possible that the test data is just weak and the solution isn’t actually correct.

(I’m also looking at my AC submission to this problem and it doesn’t seem right …)

1 Like
#3

https://oj.uz/submission/1295403

The module code does indeed pass the data with only one Dijkstra direction, but the code fails on this test case:

7 9
1 5
6 7
1 2 100
2 4 10
1 3 100
3 4 10
4 5 100
3 7 1000
5 7 1000
2 6 100
3 6 101

(correct answer being 1100)

1 Like