一道noip模拟题 高手求解 或 解释下同学的程序!

举个例子吧： 例题： 问题A：有向无环图（一个终点）中指定的点到终点间最短路径问题(最小票价) 上图为n个城市间的交通网，边上的权是票价，计算v1与V9城市间的最小票价（实际上可计算任意点到V9的最小票价）。 问题B：有向无环图（一个终点）中指定的点到终点间最长路径问题(关键路径) 工厂的工程计划用一张有向图表示（上图），有向图的顶点表示事件，有向边表示活动，边上的权表明一项活动需要的时间。上述有向图存在唯一的入度为0的开始顶点V1，表明整个计划从该事件开始；同时存在唯一的出度为0的完成顶点V9，表明该事件完成后，整个计划结束。现在的问题是，整个计划完成至少需要多少时间？ 知识点：AOV网（活动顶点网络）---条件：①存在唯一的入度为0的顶点和唯一的出度为0的顶点②有向无环图 算法讲 ①本题采用高效的动态规则法算法。 ②计算所有点的出度 ③找出所有出度=0的点的前驱点，依次处理各点，并记下新的最小值或最大值,并将该点与前驱点的出度减1 ④循环第③步，直到所有点的出度<>0 ⑤ var N:integer; A:array[1..9,1..9] of integer; Cdu,min,max:array[1..9] of integer; i,j,k:integer; begin N:=9; //共有9个点 A[1,2]:=6; A[1,3]:=4; A[1,4]:=5; A[2,5]:=1; A[3,5]:=1; A[4,6]:=2; A[5,7]:=9; A[5,8]:=7; A[5,9]:=10; A[6,8]:=4; A[7,9]:=2; A[8,9]:=4; for i:=1 to N-1 do //计算各点的出度 for j:=i+1 to N do if A[i,j]>0 then inc(Cdu[i]); for i:=1 to N do begin //最多处理N次 for j:=1 to N do if Cdu[j]=0 then break; //查找出度=0的点 for k:=1 to N do if a[k,j]>0 then begin //计算最小票价算法 if min[k]=0 then min[k]:=a[k,j]+min[j] else if min[k]>min[j]+a[k,j] then min[k]:=min[j]+a[k,j]; if max[j]+a[k,j]>max[k] then max[k]:=max[j]+a[k,j]; //计算关键路径算法 dec(Cdu[k]); dec(Cdu[j]); //点k、点j的出度减1 end; end; writeln('min=',min[1]); //输出点1到终点9的最短路径 writeln('max=',max[1]); //输出点1到终点9的最长路径 end.