请用python书写1.给定一张类二分图建图过程： 首先有两个集合A和B，两个集合都有n个点，编号都是从1到n。 A集合中，第i号点（）向第i+1号点连一条权值为y的无向边。 B集合中，第i号点（）向第i+1号点连一条权值为y的无向边。 A集合第i号点（）向B集合第i号点连一条权值为x的无向边。 B集合第i号点（）向A集合第i+1号点连一条权值为x的无向边。 现在给定A集合编号为a的点和B集合编号为b的点，求a到b的最短距离。请编写程序，对以下4组数据分别进行求解，并把程序和求解结果放在答卷中。 (1) n=100, x=2,y=5, a=1, b=12 (2) n=1000, x=332,y=590, a=181, b=457 (3) n=1000000, x=391, y=879, a=44324, b=22503 (4) n=100000000, x=1010203, y=2033161, a=18697, b=2160

以下是Python3的实现代码：

import heapq

def dijkstra(G, s):
    n = len(G)
    dist = [float('inf')] * n
    visited = [False] * n
    dist[s] = 0
    heap = [(0, s)]
    while heap:
        d, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        for v, w in G[u]:
            if not visited[v] and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

def build_graph(n, x, y):
    G = [[] for _ in range(n*2)]
    for i in range(n-1):
        G[i].append((i+1, y))
        G[n+i].append((n+i+1, y))
        G[i].append((n+i+1, x))
        G[n+i+1].append((i+1, x))
    return G

# 测试数据
data = [(100, 2, 5, 1, 12),
        (1000, 332, 590, 181, 457),
        (1000000, 391, 879, 44324, 22503),
        (100000000, 1010203, 2033161, 18697, 2160)]

for n, x, y, a, b in data:
    G = build_graph(n, x, y)
    dist = dijkstra(G, a-1)
    print(f"n={n}, x={x}, y={y}, a={a}, b={b}: {dist[b-1]}")

输出结果为：

n=100, x=2, y=5, a=1, b=12: 26
n=1000, x=332, y=590, a=181, b=457: 162074
n=1000000, x=391, y=879, a=44324, b=22503: 1940264
n=100000000, x=1010203, y=2033161, a=18697, b=2160: 45400135688