首页 > 试题广场 >

在A,B两个城市之间设有N个路站(如下图中的S1,且N10

[填空题]
在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 1  do
    begin
        s:=0;
        for i:=1 to n+1 do
        s:= 2
        g[s]:=1;j:=n+1;
        while  3  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
       4 ;
    writeln(s);
    readln;
end.

这道题你会答吗?花几分钟告诉大家答案吧!