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

为了解决这个问题，我们需要判断将某一条有向边反向后，从城市1到达城市n的最短路径是否会变短。我们可以通过计算原始图中从城市1到城市n的最短路径，并检查反转边后是否存在更短的路径来实现这一点。

方法思路

解决代码

import heapq
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    n = int(data[idx])
    idx += 1
    m = int(data[idx])
    idx += 1
    
    edges = []
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = int(data[idx])
        idx += 1
        v = int(data[idx])
        idx += 1
        c = int(data[idx])
        idx += 1
        edges.append((u, v, c))
        adj[u].append((v, c))
    
    # Compute d1: from 1
    d1 = [float('inf')] * (n + 1)
    d1[1] = 0
    heap = []
    heapq.heappush(heap, (0, 1))
    while heap:
        dist_u, u = heapq.heappop(heap)
        if dist_u > d1[u]:
            continue
        for v, c in adj[u]:
            if d1[v] > d1[u] + c:
                d1[v] = d1[u] + c
                heapq.heappush(heap, (d1[v], v))
    
    # Compute d2: from n
    d2 = [float('inf')] * (n + 1)
    d2[n] = 0
    heap = []
    heapq.heappush(heap, (0, n))
    while heap:
        dist_u, u = heapq.heappop(heap)
        if dist_u > d2[u]:
            continue
        for v, c in adj[u]:
            if d2[v] > d2[u] + c:
                d2[v] = d2[u] + c
                heapq.heappush(heap, (d2[v], v))
    
    q = int(data[idx])
    idx += 1
    output = []
    for _ in range(q):
        x = int(data[idx])
        idx += 1
        u, v, c = edges[x]
        if d2[u] == float('inf') or d1[v] == float('inf'):
            output.append("NO")
        else:
            total = d2[u] + d1[v] + c
            if total < d1[n]:
                output.append("YES")
            else:
                output.append("NO")
    
    print('\n'.join(output))
if __name__ == '__main__':
    main()

代码解释

该方法通过预处理计算最短路径，然后在线查询每条边的影响，确保了高效处理大规模数据。

转载地址：http://yrewz.baihongyu.com/