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