shortest path in color-weighted graphs
This problem seems to be NP-hard.  A reduction from 3-SAT is left as an exercise, but here is a hint.  The empty nodes are free, and then create a color for each literal and its negation.  The cost is 1 for each.  You can then visit a &quot;clause&quot; for free if and only if one of its literals is selected.  Now, the cheapest s-t-path costs $n$ if and only if the formula is satisfiable.