Suppose you have a directed graph with vertices colored A, B, C, and D. One node is $s$, the start node, and another $t$, the terminal node. You want to determine two things: First, find a path from $s$ to $t$ which contain at least one vertex of colors A, B, and C, and minimize the number of vertices of color D. Paths need not be simple.
Second, for any given $k>0$ determine whether a path exists which visits $k$-many vertices of color A, and $k$-many of color B, and $k$-many of color C. Again paths need not be simple.
Solution to the first part:
For the first question, I used the following solution: If the color at $s$ is A then we look for paths that go to a vertex colored B and then C minimizing the number of vertices colored D. Then we look for paths that go C then B minimizing the vertices colored at D. Then take the minimum of these two results. As long as we can find the minimum path for some specific color ordering in linear time, then doing it twice will still take linear time.
So to do that, first give every edge of the graph which enters a D vertex weight 1 and all others weight 0. Next make three copies of the graph, so that you have G, G', and G''. In G reassign every edge coming from an A vertex to a B to map into the corresponding vertex of G'. Then do likewise mapping B to C edges into the corresponding vertex of G''.
On this new graph run Dijkstra's. Since edges are not negative and bounded by a small constant, the algorithm runs in linear time.
To reiterate, since we can do it in some particular order of colors, we can do it then on all permutations of colors and this only multiplies linear time by a constant, so the algorithm continues to run in constant time.
I think I got the first part right but am a little more hung up on the second. I've imagined trying to leverage the solution to the first part. Perhaps make $k$ copies of the graph, on each copy run the algorithm ... but that doesn't make sense, you couldn't just stitch together two such paths and be ensured that such a path exists in the original graph. I thought maybe I should make $3k$ copies of the graph but I'm not sure how I would bind them together.
Hints or advice would be welcome.