a bit of graph dp: SPOJ - ROADS

Problem Statement:
SPOJ - ROADS

Summary:
Given a directed graph where each edge has attributes cost and distance, find the shortest distance possible from the vertex \(v_1\) to \(v_N\) while the total cost is at most \(K\).
\(N \leq 100, K \leq 10^4, |E| \leq 10^4\). Costs can be zero, and two nodes may be connected by multiple edges.

Solution:
I have two ways of solving this problem, firstly with a more intuitive and straight forward dynamic programming approach:
Let \(S(c, n)\) be the shortest distance possible to reach vertex n from vertex 1 incurring at most c total cost. Then we have S(c, n) = min [for each edge v into n] { S(c-1, n), S(c - cost[v to n]) + dist[v to n] }
But we have to take care of the case where \(c = 0\), which can be treated as a special case. We store another information of minimum distances between vertices which requires 0 cost to travel to. Then for each \(n\), after taking care of updates required for all \(c \neq 0\), we check each pairs of nodes if they are connected using 0 cost path, and update the distances accordingly.
This approach takes \(O(K(N^2+|E|))\) time, and I am surprised that it is accepted by the judge.

The better solution is using Dijkstra algorithm by modeling vertices as representing states state[vertex, total cost already incurred]. We can have the similar table \(D(n, c)\) representing the shortest distance required to travel from state[1, 0] to state[n, c]. Implementation using STL priority_queue is blazingly fast but take note that we need to terminate the algorithm once we have vertex N on top of our priority_queue since the corresponding distance is indeed the shortest distance.