SSL1624小萨的烦恼

    xiaoxiao2021-12-15  29

    SSL1624小萨的烦恼

    题目:

    圣诞节又要到了!小萨希望和自己心仪的MM一起出去度过一个浪漫的的圣诞节。他进行了详尽的准备,找到了N个很适合他们去约会的好地方,但无奈小萨和他的MM都是初三学校,晚上必须回学校上晚修,没有足够的时间让他们走遍每一个地方。迫于无奈,小萨选择了一个最合适的地方S。小萨打算和他的MM一起步行到那个地方,那样他们就有很多时间来聊天玩乐,但是无奈时间有限,小萨决定坐公共汽车过去。然而,小萨发觉,自己的钱只够买一张公共汽车车票了!小萨该怎么办呢?他找到了你……   小萨将给出一张地图,它可以看做一个有N(N<=100)个结点的图。这张地图有N个公共汽车站,小萨只可以在这N个汽车站上公共汽车。有些车站之间存在一条双向通路,无论是公共汽车还是小萨,都只能走这些通路。若两个车站之间的距离为d,步行所需要的时间为2*d秒,坐公共汽车所需要的时间为d秒。小萨他们只有T秒的时间,他希望你求出他和他的MM出去约会后能否及时赶回来,若不能,则输出“You are day dreaming!”,否则输出他们所需要花费的最少时间。 注意:一张公共汽车车票可以使用两次(只可以搭乘同一辆公共汽车),即可以认为小萨去约会地点的时间和回来的时间相等。

    题意:

    有一个n*n的地图,要从点1到点s,有一次时间减半的机会,问最短时间。

    题解:

    Floyd,用f[i,j,0]放不减半的路径,f[i,j,1]放减半的路径。

    f[i,j,0]=min(f[i,j,0],f[i,j,0]+f[i,j,0]); f[i,j,1]=min(f[i,j,1],f[i,j,1]+f[i,j,0]); f[i,j,1]=min(f[i,j,1],f[i,j,0]+f[i,j,1]); 时间复杂度:O(n*n*n)

    代码如下:

    var n,t,s,i,j,k:longint; a:array[1..100,0..100]of real; f:array[1..100,0..100,0..1]of real; begin readln(n,t,s); for i:=1 to n do for j:=1 to n do begin read(a[i,j]); if a[i,j]=0 then a[i,j]:=10000000; f[i,j,0]:=a[i,j]*2; f[i,j,1]:=a[i,j]; end; for k:=1 to n do for i:=1 to n do for j:=1 to n do begin if f[i,k,1]+f[k,j,0]<f[i,j,1] then f[i,j,1]:=f[i,k,1]+f[k,j,0]; if f[i,k,0]+f[k,j,1]<f[i,j,1] then f[i,j,1]:=f[i,k,0]+f[k,j,1]; if f[i,k,0]+f[k,j,0]<f[i,j,0] then f[i,j,0]:=f[i,k,0]+f[k,j,0]; end; if f[1,s,1]*2<=t then writeln(f[1,s,1]*2:0:0) else writeln('You are day dreaming!'); end.
    转载请注明原文地址: https://ju.6miu.com/read-1000294.html

    最新回复(0)