本文共 3855 字，大约阅读时间需要 12 分钟。

Jimmy老鼠从高处开始下落，在多个平台之间跑动，最终到达地面。为了计算他到达地面的最早时间，我们可以将问题分解为两个子问题：从左端点和右端点到地面的最短时间。每个平台的左右端点都作为新的起点，计算到达地面的最短时间。

首先，将所有平台按照高度排序。然后，定义两个数组dp_left和dp_right，分别表示从左端点和右端点到地面的最短时间。对于每个平台，检查它下方最近的平台，并计算从当前平台到下方平台的时间，加上下方平台的最短时间。选择较小的那个时间作为当前平台的最短时间。

解题思路

解决代码

import sys
def main():
    input = sys.stdin.read().split()
    idx = 0
    t = int(input[idx])
    idx += 1
    for _ in range(t):
        n = int(input[idx])
        x = int(input[idx+1])
        y = int(input[idx+2])
        max_h = int(input[idx+3])
        idx +=4
        
        platforms = []
        for _ in range(n):
            x1 = int(input[idx])
            x2 = int(input[idx+1])
            h = int(input[idx+2])
            platforms.append( (h, x1, x2) )
            idx +=3
        
        # Add the ground platform
        platforms.append( (0, -20000, 20000) )
        
        # Sort platforms by height
        platforms.sort()
        a = platforms
        
        INF = float('inf')
        dp_left = [INF] * (n + 1)
        dp_right = [INF] * (n + 1)
        
        # Process the ground platform
        dp_left[0] = 0
        dp_right[0] = 0
        
        for i in range(1, n + 1):
            h, x1, x2 = a[i]
            
            # Find the next platform below
            m = -1
            for k in range(i-1, -1, -1):
                m_h, m_x1, m_x2 = a[k]
                if m_h >= h - max_h:
                    break
                m = k
            
            if m == -1:
                if h <= max_h:
                    dp_left[i] = h
                    dp_right[i] = h
                continue
            
            # Calculate from left
            if a[m].x1 <= a[i].x1 <= a[m].x2:
                distance_left = a[i].x1 - a[m].x1
                time_left = dp_left[m] + distance_left
                if a[m].x2 >= a[i].x1:
                    time_right = dp_right[m] + (a[m].x2 - a[i].x1)
                    dp_left[i] = (h - a[m].h) + min(time_left, time_right)
            else:
                # Check if m is below i
                distance_left = a[i].x1 - a[m].x1
                time_left = dp_left[m] + distance_left
                if a[m].x2 >= a[i].x1:
                    time_right = dp_right[m] + (a[m].x2 - a[i].x1)
                    dp_left[i] = (h - a[m].h) + min(time_left, time_right)
            
            # Calculate from right
            if a[m].x1 <= a[i].x2 <= a[m].x2:
                distance_right = a[i].x2 - a[m].x2
                time_right = dp_right[m] + distance_right
                if a[m].x1 <= a[i].x2:
                    time_left = dp_left[m] + (a[m].x2 - a[i].x2)
                    dp_right[i] = (h - a[m].h) + min(time_right, time_left)
            else:
                distance_right = a[i].x2 - a[m].x2
                time_right = dp_right[m] + distance_right
                if a[m].x1 <= a[i].x2:
                    time_left = dp_left[m] + (a[m].x2 - a[i].x2)
                    dp_right[i] = (h - a[m].h) + min(time_right, time_left)
            
            if h > max_h:
                dp_left[i] = INF
                dp_right[i] = INF
        
        min_time = min(dp_left[n], dp_right[n])
        print(min_time)
if __name__ == '__main__':
    main()

代码解释