图论问题-有限制的最短路-noip对于一个图G（有向或无向）,以及两个点v1,v2,求他们符合要求的最短路径：1、在 走过的边数最少 的前提下求最短路.2、允许最多经过n条边,求最短路.3、每条边给出两个权值,在一个权值总和限制的情况下（不能超过）,求另一个权值最小的总和.简要的讲讲算法了就行了,别贴程序,我看程序最头疼.
问题描述：
图论问题-有限制的最短路-noip
对于一个图G（有向或无向）,以及两个点v1,v2,求他们符合要求的最短路径：
1、在 走过的边数最少 的前提下求最短路.
2、允许最多经过n条边,求最短路.
3、每条边给出两个权值,在一个权值总和限制的情况下（不能超过）,求另一个权值最小的总和.
简要的讲讲算法了就行了,别贴程序,我看程序最头疼.
答
其实这三个都一样,都可以这样来处理：
由于有另一限制,我们用另一个数组c[i,j]来存,i到j当前最短路径的限制值
满足：1.找到一条路径,比当前短.
2.找到一条路径,和当前长度一样,但限制值比当前小
任意一条就更新最短路,输出最后的结果就可以了...