You can find problem 8 in this pdf.

Let's color edges on a path in black and white alternatingly. Then black edges form a matching covering all vertices on a path except s and white edges form a matching covering all vertices except t. Let's build 2 copies of our graph, G₀ and G₁ for black and white matching respectively. For each v ≠ s, t v is either in both matchings or in neither. To achieve it, let's add edge v₀ - v₁ with zero cost. s should not be in black matching, so let's add new vertex s₂ and edge s₀ - s₂. s should be in white matching, so no new edges for s₁ needed. For t by similar logic we should add vertex t₂ and edge t₁ - t₂. Min cost perfect matching in this graph corresponds to shortest path with even number of edges. By the way, if we add edge t₀ - t₂ instead t₁ - t₂ we will find shortest path with odd number of edges. Also this solution doesn't work with negative edges, any ideas on how to fix it?

First, take all negative edges. Let's delete all vertices covered by them. If there was an edge connecting uncovered and covered vertex, let's say that now it connects uncovered vertex to itself. Now all edges are nonnegative.

Let's look at the answer. If there is a path of length at least 3 then we can delete the middle edge on this path and our answer will improve. It means in optimat answer each connected component is a star(possibly with a single edge). For each star let's choose one edge in it. Then chosen edges form a matching. For all vertices not in this matching it's optimal to choose the shortest edge incident to that vertex. Let's build 2 copies of the graph and for each vertex v connect v₀ and v₁ with an edge with weight equal to the shortest edge incident to v multiplied by 2. Then the answer is min weight matching divided by 2.

For each edge v - u let's create separate copies of vertices v and u. For each vertex v our matching should contain exactly 2 edges incident to v. Let's create deg(v) - 2 additional vertices and connect them to all copies of v we created with 0 weight edges. Now perfect matching will match those deg(v) - 2 vertices to deg(v) - 2 copies of v and other 2 copies will correspond to edges in cycle cover.

Let's prove that the answer from the above post is correct. It suffices to show that given a matching $$$M$$$ where each matched pair in $$$M$$$ is incomparable, we can remove all vertices in $$$n-|M|$$$ rounds.

Specifically, we will describe how to remove vertices and modify $$$M$$$ such that $$$n-|M|$$$ decreases by exactly one during the first round. Let $$$S_0$$$ be the set of all vertices with in-degree 0.

Case 1: $$$S_0$$$ contains a vertex not in $$$M$$$.

Remove any such vertex in the first round.

Case 2: $$$S_0$$$ contains a pair of vertices matched in $$$M$$$.

Remove any such matched pair in the first round.

Case 3: All vertices in $$$S_0$$$ are matched, but $$$S_0$$$ does not contain a matched pair.

Given $$$v\in S_0$$$, let $$$m(v)$$$ denote the vertex matched with $$$v$$$ in $$$M$$$ (note that $$$m(v)\not\in S_0$$$).

Lemma: There exist $$$a,b\in S_0$$$ such that $$$m(a)$$$ and $$$m(b)$$$ are incomparable.

If the lemma holds, then we can remove $$$(a,m(a)), (b,m(b))$$$ from $$$M$$$ and insert $$$(a,b), (m(a),m(b))$$$ into $$$M$$$, reducing to case 2. It remains to prove the lemma.

Proof of lemma: Let $$$x\leadsto y$$$ mean that there is a directed path from $$$x$$$ to $$$y$$$ in the original DAG; then $$$x$$$ and $$$y$$$ are incomparable if $$$x\not\leadsto y$$$ and $$$y\not\leadsto x$$$. Now let's construct a new directed graph $$$D$$$ on $$$S_0$$$ where $$$x\to y$$$ in $$$D$$$ if $$$y\leadsto m(x)$$$. Since every vertex in $$$D$$$ has out-degree at least 1 and $$$D$$$ has no self-loops, $$$D$$$ must have a directed cycle $$$v_0\to v_1 \to \dots v_{k-1}\to v_0$$$ with $$$k>1$$$ and all $$$v_i$$$ distinct. Since $$$v_{(i+1)\pmod k}\leadsto m(v_i)$$$ and $$$v_{(i+1)\pmod k}\not \leadsto m(v_{(i+1)\pmod k})$$$, we must have $$$m(v_i)\not\leadsto m(v_{(i+1)\pmod k})$$$ for all $$$i$$$. Also, there must exist some $$$j$$$ such that $$$m(v_{(j+1)\pmod k})\not\leadsto m(v_j)$$$, or the original DAG would contain a cycle. Then $$$m(v_j)$$$ and $$$m(v_{(j+1)\pmod k})$$$ are incomparable, so the lemma is proven.

If we assume that the special edges are the perfect matching of the graph, the problem is equivalent of determining unique matching. (More specifically, it asks for a "counterexample" if the graph does not have a unique perfect matching.) Unique perfect matching can be determined by calling the maximum matching algorithm $$$O(N)$$$ times, but there is a well-known characterization that the 2-connected graph can't have a unique matching. I think this illustrates the difference between my solution and the official solution.