UC知道区间图最短路问题 pascal高手进
来源：百度知道 编辑：UC知道 时间：2024/06/14 20:09:40
区间图最短路问题
(inter.pas)
【背景描述】
S 是直线上n 个带权区间的集合。从区间IS 到区间JS 的一条路是S 的一个区间序列J(1)，J(2)，…，J(k)，其中J(1) = I，J(k) = J，且对所有1i k-1, J(i)与J(i+1)相交。这条路的长度定义为路上各区间权之和。在所有从I 到J 的路中，路长最短的路称为从I 到J的最短路。带权区间图的单源最短路问题要求计算从S 中一个特定的源区间到S 中所有其它区间之间的最短路。
【输入】
文件的第1 行是正整数n，表示有n个带权区间(n<400000)。第2行起每行有3 个正整数，分别表示带权区间的左端点，右端点和区间的权值。(n 和直线长度为 longint)
【输出】
程序结束时，将计算出的最左区间到所有区间的最短路之和输出到文件中。当最左区间与区间i 不连通时，最左区间与区间i 之间的最短路不计入。
【样例输入】
10
1 4 15
5 6 12
3 7 13
2 9 17
10 13 17
12 14 19
11 15 21
16 18 13
17 19 15
8 20 18
【样例输出】
500
(inter.pas)
【背景描述】
S 是直线上n 个带权区间的集合。从区间IS 到区间JS 的一条路是S 的一个区间序列J(1)，J(2)，…，J(k)，其中J(1) = I，J(k) = J，且对所有1i k-1, J(i)与J(i+1)相交。这条路的长度定义为路上各区间权之和。在所有从I 到J 的路中，路长最短的路称为从I 到J的最短路。带权区间图的单源最短路问题要求计算从S 中一个特定的源区间到S 中所有其它区间之间的最短路。
【输入】
文件的第1 行是正整数n，表示有n个带权区间(n<400000)。第2行起每行有3 个正整数，分别表示带权区间的左端点，右端点和区间的权值。(n 和直线长度为 longint)
【输出】
程序结束时，将计算出的最左区间到所有区间的最短路之和输出到文件中。当最左区间与区间i 不连通时，最左区间与区间i 之间的最短路不计入。
【样例输入】
10
1 4 15
5 6 12
3 7 13
2 9 17
10 13 17
12 14 19
11 15 21
16 18 13
17 19 15
8 20 18
【样例输出】
500
恩，这个题乍一看好像可以用Kruskal或Prim算法
但是，仔细一分析，是一道DP的题目……^0^
其动归方程如下：
f[1,j]=Min{f[1,j-1],f[1,p]+f[p,j](p:=2 to j-1)}
暂时先写个方程吧~如果楼主没有看懂或想要优化算法的话，请补充一下问题
我会提供优化算法或是源代码～