不是VIP会员,不能显示答案

题目解答

题目:
在A,B两个城市之间设有N个路站(如下图中的S1,且N<100),城市与路站之间、路站和路站之间各有若干条路段(各路段数≤20,且每条路段上的距离均为一个整数)。A,B的一条通路是指:从A出发,可经过任一路段到达S1,再从S1出发经过任一路段,…最后到达B。通路上路段距离之和称为通路距离(最大距离≤1000)。当所有的路段距离给出之后,求出所有不同距离的通路个数(相同距离仅记一次)。

例如:下图所示是当N=1时的情况:从A到B的通路条数为6,但因其中通路5+5=4+6,所以满足条件的不同距离的通路条数为5。

算法说明:本题采用穷举算法。
数据结构:N:记录A,B间路站的个数
数组D[I,0]记录第I-1到第I路站间路段的个数
D[I,1],D[I,2],…记录每个路段距离
数组G记录可取到的距离
程序清单:
program chu2; 
var i,j,n,s:integer; 
    b:array[0..100]of integer; 
    d:array[0..100,0..20]of integer; 
    g:array[0..1000]of 0..1;
begin
    readln(n); 
    for i:=1 to n+1 do
    begin
        readln(d[i,0]); 
        for j:=1 to d[i,0] do readln(d[i,j]); 
    end; 
    d[0,0]:=1;
    for i:=1 to n+1 do b[i]:=1;
    b[0]:=0;
    for i:=0 to 1000 do g[i]:=0; 
    while b[0]=0  do
    begin 
        s:=0; 
        for i:=1 to n+1 do 
        s:=s+d[i,b[i]]; 
        g[s]:=1;j:=n+1; 
        while  b[j]=d[j,0]  do  j:=j-1; 
        b[j]:=b[j]+1; 
        for i:=j+1 to n+1 do b[i]:=1; 
    end; 
    for i:=1 to 1000 do 
       s:=s+g[i] ; 
    writeln(s); 
    readln; 
end. 
考点:
分析:
解答:
评论:
老师: