[白準10217 Python]KCMトラベル(Gold 1,DP)

アルゴリズムタイプ:DP(裸)
草は参考にならずに自分で解いたのか.X
https://www.acmicpc.net/problem/10217

SOLVE 1

전체 문제를 "출발 노드에서 row 노드까지 정확히 비용 column으로 갈 때의 최단 시간"으로 둘 때의 풀이

import sys
import math
input = sys.stdin.readline
INF = math.inf

for _ in range(int(input())):
    N, M, K = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    knapsack = [[INF]*(M+1) for _ in range(N+1)]
    knapsack[1][0] = 0 # 출발 노드의 최단 시간 값 0으로 초기화
    
    for _ in range(K):
        u, v, c, d = map(int, input().split())
        graph[u].append((v, c, d))
    
    # 비용 0부터 시작하여 1씩 올리면서, 비용 K를 사용했을 때(column)
    # 어떤 노드(row)까지 도달하는 최단 시간 값이 존재하고 있다면(not INF),
    # 그 노드의 인접 노드들의 최단 시간 값을 비교&갱신해준다.
    for cost in range(M+1):
        for city in range(1, N+1):
            if knapsack[city][cost] != INF:
                for adjacency_city, c, d in graph[city]:
                    cal_d = knapsack[city][cost] + d
                    cal_c = cost + c
                    
                    # 인접 노드로 이동하고 난 비용이 M 이하여야함.
                    if cal_c <= M and cal_d < knapsack[adjacency_city][cal_c]:
                        knapsack[adjacency_city][cal_c] = cal_d
    
    # 비용 0을 사용하여 N으로 가는 최단 시간, 비용 1을 사용하여, ..., 이들 중
    # 최소인 값을 채택하여 답으로 확정
    result = min(knapsack[N])
    
    if result == INF:
        print("Poor KCM")
    else:
        print(result)

SOLVE 2

전체 문제를 "출발 노드에서 row 노드까지 예산 column 내의 비용으로 갈 때의 최단 시간"으로 둘 때의 풀이

import sys
from collections import deque
input = sys.stdin.readline

def solution():
    INF = float('inf')
    for _ in range(int(input())):
        N, M, K = map(int, input().split())
        graph = [[] for _ in range(N+1)]
        knapsack = [[INF]*(M+1) for _ in range(N+1)]

        if M == 0:
            print("Poor KCM")
            continue

        for _ in range(K):
            u, v, c, d = map(int, input().split())
            graph[u].append((v, c, d))

        knapsack[1][0] = 0 # 출발 노드의 최단 시간 값 0으로 초기화
        q = deque([(1, 0, 0)]) # 출발 노드에서부터 BFS 탐색

        while q:
            cnt_city, cnt_cost, cnt_time = q.popleft()

            if cnt_time > knapsack[cnt_city][cnt_cost]:
                continue

            for adc_city, adc_cost, adc_time in graph[cnt_city]:
                cal_cost = cnt_cost + adc_cost
                cal_time = cnt_time + adc_time

                if cal_cost <= M and cal_time < knapsack[adc_city][cal_cost]:
                    # 전체 문제 정의에 의해, 냅색 메모이제이션 리스트에서
                    # 원소가 "예산 column 이하의 비용을 사용하여 가는 최단 거리"이므로
                    # K 비용으로 가능한 최단 경로는 K+1 ~ M 비용에 대해서도 당연히 가능
                    # 하므로 비교 & 갱신해줘야한다.
                    for cost in range(cal_cost, M+1):
                        if cal_time < knapsack[adc_city][cost]:
                            knapsack[adc_city][cost] = cal_time
                        else:
                            break
                    q.append((adc_city, cal_cost, cal_time))
                
        print(knapsack[N][M] if knapsack[N][M] != INF else 'Poor KCM')

if __name__ == '__main__':
    solution()

緒論
この問題は一見多学科の問題のように見える.特定のノードから特定のノードまでの最短時間(重み付け)を求めるのが目的なので、幹線の重み付けはすべて正の値です.
しかし,エッジ弛緩がうまくいかない多芸団方式の部分も存在する.
条件上、空港から空港まで「料金」の値があります.
これはM以下の条件なので、多段で求めた最短時間の料金がMを超えると、この値は答えではありません.
すなわち,あるノードにアクセスしていない隣接ノードでは,開始ノードから到達する最短時間値が最も小さい隣接ノードを選択しなければならないが,コストも考慮しなければならない条件であるため,どのノードがすべての条件に合致する最短経路であるかを判断することができず,深く探索することができない.
これは多翼点アルゴリズムでは解くことができないことを意味する.
じゃ、別の道を探しましょう.
条件を見て、料金はM以下です.これは気まずい問題でよく見られるパターンです.DPアルゴリズムを用いてこの問題を解決した.
この問題は全体の問題を2つの程度に定義することができ、異なる答えも異なる.詳細については以下を参照してください.
SOLVE 1)プールの概要(問題全体を「開始ノードから行ノードまでの正確さからコスト列までの最短時間」に設定した場合のプール)

ちなみに、この解答はpypy 3で提出しなければ通過できません.
問題全体を「開始ノードからrowノードまでの正確なコスト列までの最短時間」と定義すると、明示的な注釈配列の行はノード番号であり、列はコストです.(最終的に返される正解の形状は、問題の書き出し値全体にわたってさらに加工する必要があります.後述)

問題全体が、シェーディングアノテーション配列の要素値が何を意味するかをすぐに隠します.
問題全体を部分的に分ける.출발 노드에서 row 노드까지 정확히 비용 K로 갈 때의 최단 시간 = row 노드의 인접 노드 a, b, c, d, ...들에 대하여, 이 중 임의의 인접 노드 P에서 row 노드로 갈 때의 비용과 시간이 c, t일 때, <출발 노드에서 임의의 인접 노드 P까지 비용 K-c로 가는 최단 시간 + t> 값을 mid라고 하자. 이 때 모든 인접 노드들의 mid 값 중 최소 값

これを基準に上向きに計算して答えを求めると,出発ノードからグラフを見続け,Daestraの実行形式と同様に更新する.
もちろん,深く探索する必要はないのでBFS形式で探索すればよいが,そのノード(前のノードから比較&更新されたノード)が元の暗色値より大きい場合はconitnueであり,比較と更新の部分は多翼点と同じである.
しかし、このような方法で解決すると、時間の複雑さに時間がかかります.おそらくインデックスの使用に時間がかかります.
したがって,このソリューションに加えて,他の一時停止方式が採用されている.

費用0～(列0)の最短時間値が存在するすべてのノードについて、隣接ノードの最短時間値を比較して更新し(開始ノード費用+隣接ノードの費用値<=Mでのみ更新)、費用1で同じタスクを実行し、費用2を費用Mまで実行します.
このように求めた最適解が一般解であるのは,費用C,最短時間値Tの(C行T列)ノードに対して隣接ノードにedge releaseを行うと,すべての幹線の時間値が正の値となり,必然的に最短時間値が等しいかそれ以上になるためである.
すなわち,左側列の値は右側列の値に影響を与える構造であるため,左側から右側列に更新する方式を実行する際には一般解が保障されているようである.
その後、1~Mの料金で、N番空港行きのすべての最短時間値に最小値を出力すればよい.

SOLVE 2プールの概要(問題全体を「開始ノードから行ノードまでの予算列の最短時間」に設定)

問題全体を「開始ノードからrowノードまで、予算列内のコストで計算した最短時間」にまとめると、columnの予算からrowノードまでの最短時間Tを使用できる場合は、予算を超える場合は、もちろん遅くてもT時間内に到着できることに注意してください.
すなわち、edge releaseが実行されると、発色注釈配列のC列が更新されると、C+1列、C+2列、…これは、M列をすべて比較して更新することを意味します.

草は1番から時間をかけて、採用していない方法で探索し、リラックスしながら行えばいいのです.
その前に、まず問題全体と一部の問題を理解してください.
出発ノードからrowノードから予算Kまでの最短時間はtime(row,K)である.time(row, K) = min(time(row, K-1), row 노드의 인접 노드 a, b, c, d, ...들에 대하여, 이 중 임의의 인접 노드 P에서 row 노드로 갈 때의 예산과 시간이 c, t일 때, <출발 노드에서 임의의 인접 노드 P까지 예산 K-c 이내로 가는 최단 시간 + t> 값을 mid라고 하자. 이 때 모든 인접 노드들의 mid 값 중 최소 값)

のすべての問題を基準に変換するために、先頭ノードから隣接ノードの比較と更新を開始するが、当時の予算KとK+1~Mの最短時間値の比較と更新を忘れないでください.

この問題から分かる事実は,まずこのプールがpython 3でコミットされてもACが表示されることである.しかし,コード全体を関数に入れて実行すると,少し変えると時間の複雑さは半分程度減少する.
関数にはlocalscopeがあるため、関数で宣言される変数はゾーン変数です.これは、実行時に追加できないためarrayに格納するのが速く、global scopeで宣言されるグローバル変数は実行時のディックシーケンスに追加され、格納と読み取り速度が比較的遅いためです.

勉強するところ、難しいところ

条件付けを見て、「Da」と「Da」と「Da」の色が似ているだけを解くのは難しいと思いました.最初は「Da」と「Da」の混合を考えました
しかし、問題は最初はドエストラアルゴリズムを直接適用することはできませんでした.どうやら、注釈配列の行、列はよくできていますが、要素値の定義、すなわち問題全体と局所的な問題はよくできません.
DPで最短パスを求めたことがないので難しいです.今回の経験を機に、いくつかの対処法を身につけたようです.