COCI 2020/2021 #6 题解

思路

由瞪眼法得知, 此题为非负权全源最短路, 最优做法是Dijkstra跑N遍或Johnson, 此处使用更常见的Dijkstra算法.

题解代码

import heapq
from collections import defaultdict
from functools import cache


def dij_builder(e):  # 构建Dijkstra算法
    @cache  # 缓存结果
    def dijkstra(s):  # Dijkstra模板
        vis = set()
        queue = [(0, s)]
        dis = defaultdict(lambda: float("+inf"))
        dis[s] = 0
        while queue:
            _, u = heapq.heappop(queue)
            if u in vis:
                continue
            vis.add(u)
            for v, w in e[u]:
                if dis[v] > dis[u] + w:
                    dis[v] = dis[u] + w
                    heapq.heappush(queue, (dis[v], v))
        return dis

    return dijkstra


e = defaultdict(list) # 初始化邻接表

n, m = map(int, input().split())
for i in range(m):
    a, b, t = input().split()
    e[a].append((b, int(t))) # 构建图

dijkstra = dij_builder(e) # 以图初始化Dijkstra算法

for i in range(int(input())): # 求解和结果输出
    a, b = input().split()
    if dijkstra(a)[b] < float("+inf"):
        print(dijkstra(a)[b])
    else:
        print("Roger")