title: Shortest path on graph with changing weights
body: <p>I was trying to solve a local programming contest question. The problem is basically about finding the shortest path in a weighted graph. I am pretty new to these types of problems and I thought I could use Dijkstra's algorithm. However, there is a small complication - certain values are different, depending on the situation of this current path.</p>
  
  <p><strong>Problem</strong></p>
  
  <p>There are two types of weights: normal weights and weights with condition (let's call them K). The condition is this: once you move through edge with weight K, all other weights of type K have value of 0. This brings a few more problems, because the apparent shortest path can be beaten by a combination of edges with weights of type K.</p>
  
  <p><strong>Example</strong></p>
  
  <p>Below is this type of problem. If no weights would change their value, we could find the shortest path easily with Dijkstra. However, when weights K change their value, we can find a shorter path, because the weight of the edge C-D is 0 after moving through the edge A-C.
  <a href="https://i.stack.imgur.com/3ELbx.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/3ELbx.jpg" alt="enter image description here"></a></p>
  
  <p><strong>Question</strong></p>
  
  <p>How can I find the shortest path?</p>
  
  <p>Can I use Dijkstra's algorithm here or is it better to use another algorithm like A* or BFS?</p>