##一道DP题

无向图G有N个结点，它的边上带有距离和花费S[i]。

要求你在花费100元以内，从结点1走到结点N，经过的路径最短。

###分析

求在花费最少情况下的最短路径

不考虑花费的最短路径不是所求的路径

记录到达i结点并且花费j的最短路径DP[i][j]

最后的结果是DP[N-1][0-M]的最小值

时间复杂度O(N*N*M)

###子问题

不考虑到同一结点最短距离所花的最少钱,最短距离只有一种,所花的最少钱不能推出后面的问题,不是子问题

考虑花费同等价格到同一结点的最短路径.花费同等价格当然得走最短路径.是子问题

子问题:到X结点花费在M以内的最小距离.花费小于M的最小距离都要记录

最后问题:到N结点花费在M以内的最小距离.花费1元1米到A,花费2元2米到B, A到N花费3元1米 B到N花费1元1米.最后到N花费4元2米\3元3米.身上有10元,取方案1,花费4元2米

###递推公式 DP[i][j]表示花费j元,从0出发到i,走最短的路.意味着花费j元只有这条路最短.

DP[i][j] = min(DP[k][j+S[k]]+dist[k][i]) (j+S[k]<=M) 遍历j,和与i相邻的结点