[Homework 3] 小仔坐飛機

[alemapnil]

提交連結

https://judge.ccclub.io/status/c26d99ed7da91468613f3b1384d96810

程式碼

L1 = [int(i) for i in input().split(' ')]
spot_n, tran, a1, b1 = L1[0], L1[1], L1[2], L1[3]

if a1 > b1:
    des=a1
    start=b1
else:
    des=b1
    start=a1
    

price_check = {} #紀錄所有點到點的價錢
for S, spot in enumerate(range(spot_n)):    
    if S == spot_n - 1:
        break
    copy_n = range(spot_n)[S + 1 : ]
    in_p = [int(i) for i in input().split(' ')]
    for C, copy in enumerate(copy_n):
        price_check[(spot,copy)] = in_p[C]
routes = [t for t in price_check] #紀錄所有點到點的路徑，gragh上所有的邊

O_edges = {} #任一點連結的所有邊
for route in routes:
    fm, to = route[0], route[1]
    if fm not in O_edges:
        O_edges[fm] = [to]
    else:
        O_edges[fm].append(to)

nodes = [node for node in O_edges if des > node >= start] #從起點到終點經過的所有點
edges = {} #從起點到終點經過的所有點之各個邊
for n in nodes:
    edges[n] = O_edges[n]

des_path = [] #所有從起點到終點的路線
stack = [start]
while stack:
    def recurse(para):
        vtx = stack[-1]
        for node in edges[vtx]:
            stack.append(node)

            if stack[-1] == des:
                copy = stack.copy()
                des_path.append(copy)
                stack.pop()
            
            if node in edges:
                recurse(node)
            else:
                stack.pop()
    recurse(stack[-1])

qulified=[ path for path in des_path if len(path) <= tran + 2]  #最大轉乘次數以內的路徑
dic = {} # #最大轉乘次數以內的路徑，對應的價錢
for q in qulified:
    total = 0
    for P, path in enumerate(q):
        slice = tuple(q[P:P + 2])
        if len(slice) == 2:
            total += price_check[slice]
    dic[tuple(q)] = total

ans = min(dic.values())
print(ans)

錯誤訊息

WA

問題描述

我的算法是收集所有從起點到終點的所有可能路徑，之後再限制轉乘次數，得來的路徑為合格路徑，再一一計算合格路徑對應的價錢，然後找最小值。我有考量s>d的input，若是這樣，s設為終點，d設為起點，總之程式強制將終點數值大於起點，然後只算單向情況，因為再怎麼樣也不會發生折返問題，若有折返也不會是答案，因為不是最小值。測資都對，尤其是路徑的收集都沒問題，為何是WA? 請助教指點，由於已快臨界截止日期，可否請助教速速回覆呢? 麻煩了謝謝🙏

[alemapnil]

@St-Ren @yichensu @dada8397

[alemapnil]

@St-Ren @yichensu @dada8397 請助教指點一下，感謝

[St-Ren]

關於這題，目前你錯誤的測資其中之一是

11 5 0 10
9259 6942 3051 3015 3821 55 3471 3431 8344 2853
8582 8653 3257 9195 77 4445 3884 33 9058
5437 3343 3880 4996 5709 5555 88 10
6868 6441 2673 8947 3626 9240 4292
3585 7510 3074 8747 2166 5952
6658 8935 3242 8759 4738
5852 9171 4901 9841
9074 8259 3958
9870 7617
8082

，此外，你還有一個測資是 TLE 的情況，可能是因為還沒到目標複雜度 O(In^2)，請再分析一下你各區段的程式碼複雜度，思考如何精簡他。

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.