Submission #22131725

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def main():
    N = int(input())
    city = [[0] * 3 for i in range(N)]
    for i in range(N):
        city[i][0],city[i][1],city[i][2] = map(int, input().split())
    inf = 10**20
    dp = [[inf] * N for i in range(1<<N)]#各状態と最終都市を表したリスト
    dp[1][0] = 0 #スタート地点のコストを0に
    for s in range(1,1<<N):#集合を添字の小さい順に試す
        for i in range(N):#現地点の都市
            if dp[s][i]!=inf:#到達しているパターンであれば、現地点から到達地点へのコストを求める
                for j in range(N):#行先都市
                    t = s|(1<<j)
                    if s==t:#現地点と到達地点が同じであれば計算不要なためcontinue
                        continue
                    a,b,c = city[i]
                    p,q,r = city[j]
                    cost = abs(p - a) + abs(q - b) + max(0, r - c)
                    if dp[t][j] > dp[s][i]+cost:
                        dp[t][j] = dp[s][i]+cost
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

def main():
    N = int(input())
    city = [[0] * 3 for i in range(N)]
    for i in range(N):
        city[i][0],city[i][1],city[i][2] = map(int, input().split())

    inf = 10**20
    dp = [[inf] * N for i in range(1<<N)]#各状態と最終都市を表したリスト
    dp[1][0] = 0 #スタート地点のコストを0に
    for s in range(1,1<<N):#集合を添字の小さい順に試す
        for i in range(N):#現地点の都市
            if dp[s][i]!=inf:#到達しているパターンであれば、現地点から到達地点へのコストを求める
                for j in range(N):#行先都市
                    t = s|(1<<j)
                    if s==t:#現地点と到達地点が同じであれば計算不要なためcontinue
                        continue
                    a,b,c = city[i]
                    p,q,r = city[j]
                    cost = abs(p - a) + abs(q - b) + max(0, r - c)
                    if dp[t][j] > dp[s][i]+cost:
                        dp[t][j] = dp[s][i]+cost
    ans = 10**20
    #上記処理で全ての地点を回った時のコストが分かる
    #その場所から1の地点に戻った際のトータルコストが低いものが答え
    for i in range(N):
        a,b,c = city[i]
        p,q,r = city[0]
        cost = abs(p - a) + abs(q - b) + max(0, r - c)
        ans = min(ans,dp[-1][i]+cost)
    return ans

print(main())    

Submission Info

Judge Result