头像

皓首不倦


访客:2044

在线 



皓首不倦
1小时前

'''
Prim 最小生成树算法
'''


# 普利姆算法求解最小生成树输入为边列表,每条边表示为(起点,终点,权重)
# 返回最小生成树权重总和,以及最小生成树边列表, 生成不了最小生成树返回None

from queue import PriorityQueue
def getMinSpanTreePrim(edges):
    if len(edges) == 0:
        return [0, []]

    span_tree = []
    node_set = set()
    link = {}
    for a, b, w in edges:
        node_set.add(a)
        node_set.add(b)

        if a not in link:
            link[a] = []
        if b not in link:
            link[b] = []

        link[a].append((b, w))
        link[b].append((a, w))

    node = None
    sum = 0

    min_heap = PriorityQueue()
    visited = set()
    for _ in range(len(node_set)):
        if node is None:
            node = edges[0][0]
            visited.add(node)
            for next, w in link[node]:
                min_heap.put((w, node, next))
        else:
            while True:
                if min_heap.empty():
                    return [None, None]

                w, node1, node2 = min_heap.get()
                if not (node1 in visited and node2 in visited):
                    sum += w
                    span_tree.append((node1, node2))

                    for node in [node1, node2]:
                        if node not in visited:
                            visited.add(node)
                            for next, w in link[node]:
                                min_heap.put((w, node, next))

                    break

    return [sum, span_tree] if len(span_tree) == len(node_set) - 1 else [None, None]


n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b, w = map(int, input().split())
    edges.append((a, b, w))
ans = getMinSpanTreePrim(edges)
print(ans[0] if ans[0] is not None else 'impossible')





皓首不倦
1小时前

'''
Prim 最小生成树算法
'''


# 普利姆算法求解最小生成树输入为边列表,每条边表示为(起点,终点,权重)
# 返回最小生成树权重总和,以及最小生成树边列表, 生成不了最小生成树返回None

from queue import PriorityQueue
def getMinSpanTreePrim(edges):
    if len(edges) == 0:
        return [0, []]

    span_tree = []
    node_set = set()
    link = {}
    for a, b, w in edges:
        node_set.add(a)
        node_set.add(b)

        if a not in link:
            link[a] = []
        if b not in link:
            link[b] = []

        link[a].append((b, w))
        link[b].append((a, w))

    node = None
    sum = 0

    min_heap = PriorityQueue()
    visited = set()
    for _ in range(len(node_set)):
        if node is None:
            node = edges[0][0]
            visited.add(node)
            for next, w in link[node]:
                min_heap.put((w, node, next))
        else:
            while True:
                if min_heap.empty():
                    return [None, None]

                w, node1, node2 = min_heap.get()
                if not (node1 in visited and node2 in visited):
                    sum += w
                    span_tree.append((node1, node2))

                    for node in [node1, node2]:
                        if node not in visited:
                            visited.add(node)
                            for next, w in link[node]:
                                min_heap.put((w, node, next))

                    break

    return [sum, span_tree] if len(span_tree) == len(node_set) - 1 else [None, None]


n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b, w = map(int, input().split())
    edges.append((a, b, w))
ans = getMinSpanTreePrim(edges)
print(ans[0] if ans[0] is not None else 'impossible')




活动打卡代码 AcWing 854. Floyd求最短路

皓首不倦
2小时前

n, m, q = map(int, input().split())
edges = {}
for i in range(m):
    a, b, w = map(int, input().split())
    if a == b:
        continue

    if (a, b) not in edges:
        edges[(a, b)] = w
    else:
        edges[(a, b)] = min(edges[(a, b)], w)


dis = [[0x7fffffff]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    dis[i][i] = 0
for (a, b), w in edges.items():
    dis[a][b] = w


for t in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            dis[a][b] = min(dis[a][b], dis[a][t] + dis[t][b], 0x7fffffff)
            if dis[a][b] >= 0x7fffffff // 2:
                dis[a][b] = 0x7fffffff

for _ in range(q):
    a, b = map(int, input().split())
    print('impossible' if dis[a][b] == 0x7fffffff else dis[a][b])



皓首不倦
2小时前



n, m, q = map(int, input().split())
edges = {}
for i in range(m):
    a, b, w = map(int, input().split())
    if a == b:
        continue

    if (a, b) not in edges:
        edges[(a, b)] = w
    else:
        edges[(a, b)] = min(edges[(a, b)], w)


dis = [[0x7fffffff]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    dis[i][i] = 0
for (a, b), w in edges.items():
    dis[a][b] = w


for t in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            dis[a][b] = min(dis[a][b], dis[a][t] + dis[t][b], 0x7fffffff)
            if dis[a][b] >= 0x7fffffff // 2:
                dis[a][b] = 0x7fffffff

for _ in range(q):
    a, b = map(int, input().split())
    print('impossible' if dis[a][b] == 0x7fffffff else dis[a][b])




活动打卡代码 AcWing 852. spfa判断负环

皓首不倦
3小时前
'''
SPFA算法,解带负权边的有向图和不带负权边的无向图的单源
最短路问题
'''
from collections import deque

class SPFA:

    # start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
    def __init__(self, edges, is_directed, max_node_num):
        self.edges = edges[::]
        self.is_directed = is_directed
        self.max_node_num = max_node_num

    # 获取最短路径长度的列表[(节点1,长度1), (节点2, 长度2) .....]
    def getMinPathLen(self):
        return self.getMinInfo()

    def getMinInfo(self):
        link = {}
        dis = [0x7fffffff] * (self.max_node_num+1)

        for a, b, w in self.edges:
            if not self.is_directed:
                # 无向图检查是否有负边
                if w < 0:
                    return None

                if a not in link:
                    link[a] = []
                if b not in link:
                    link[b] = []

                link[a].append((b, w))
                link[b].append((a, w))

            else:
                if a not in link:
                    link[a] = []
                link[a].append((b, w))


        updated_nodes = deque()
        for i in range(1, self.max_node_num+1):
            updated_nodes.append(i)
        in_que = [1] * (self.max_node_num + 1)


        # 进行V次迭代,第V次检查是否是无解情况
        iter_times = 0
        while iter_times < self.max_node_num:
            update_flag = False

            # 利用上一轮迭代距离变小的点进行松弛操作
            node_num = len(updated_nodes)
            for _ in range(node_num):
                a = updated_nodes.popleft()
                in_que[a] = 0
                if a not in link:
                    continue

                for b, w in link[a]:
                    new_dis = 0x7fffffff if dis[a] == 0x7fffffff else dis[a] + w
                    if new_dis < dis[b]:
                        dis[b] = new_dis
                        update_flag = True

                        if in_que[b] == 0:
                            in_que[b] = 1
                            updated_nodes.append(b)

            iter_times += 1

            if iter_times == self.max_node_num:
                if update_flag:
                    return None

            if not update_flag:
                break

        return [[node, dis[node]] for node in range(1, self.max_node_num+1)]



n, m = map(int, input().split())
edges = {}
for _ in range(m):
    a, b, w = map(int, input().split())
    if (a, b) not in edges:
        edges[(a, b)] = w
    else:
        edges[(a, b)] = min(edges[(a, b)], w)

edges = [(a, b, w) for (a, b), w in edges.items()]

flag = False
algo = SPFA(edges, is_directed=True, max_node_num = n)
ans = algo.getMinPathLen()
if ans is None:
    flag = True

print('Yes' if flag else 'No')



皓首不倦
3小时前


'''
SPFA算法,解带负权边的有向图和不带负权边的无向图的单源
最短路问题
'''
from collections import deque

class SPFA:

    # start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
    def __init__(self, edges, is_directed, max_node_num):
        self.edges = edges[::]
        self.is_directed = is_directed
        self.max_node_num = max_node_num

    # 获取最短路径长度的列表[(节点1,长度1), (节点2, 长度2) .....]
    def getMinPathLen(self):
        return self.getMinInfo()

    def getMinInfo(self):
        link = {}
        dis = [0x7fffffff] * (self.max_node_num+1)

        for a, b, w in self.edges:
            if not self.is_directed:
                # 无向图检查是否有负边
                if w < 0:
                    return None

                if a not in link:
                    link[a] = []
                if b not in link:
                    link[b] = []

                link[a].append((b, w))
                link[b].append((a, w))

            else:
                if a not in link:
                    link[a] = []
                link[a].append((b, w))


        updated_nodes = deque()
        for i in range(1, self.max_node_num+1):
            updated_nodes.append(i)
        in_que = [1] * (self.max_node_num + 1)


        # 进行V次迭代,第V次检查是否是无解情况
        iter_times = 0
        while iter_times < self.max_node_num:
            update_flag = False

            # 利用上一轮迭代距离变小的点进行松弛操作
            node_num = len(updated_nodes)
            for _ in range(node_num):
                a = updated_nodes.popleft()
                in_que[a] = 0
                if a not in link:
                    continue

                for b, w in link[a]:
                    new_dis = 0x7fffffff if dis[a] == 0x7fffffff else dis[a] + w
                    if new_dis < dis[b]:
                        dis[b] = new_dis
                        update_flag = True

                        if in_que[b] == 0:
                            in_que[b] = 1
                            updated_nodes.append(b)

            iter_times += 1

            if iter_times == self.max_node_num:
                if update_flag:
                    return None

            if not update_flag:
                break

        return [[node, dis[node]] for node in range(1, self.max_node_num+1)]



n, m = map(int, input().split())
edges = {}
for _ in range(m):
    a, b, w = map(int, input().split())
    if (a, b) not in edges:
        edges[(a, b)] = w
    else:
        edges[(a, b)] = min(edges[(a, b)], w)

edges = [(a, b, w) for (a, b), w in edges.items()]

flag = False
algo = SPFA(edges, is_directed=True, max_node_num = n)
ans = algo.getMinPathLen()
if ans is None:
    flag = True

print('Yes' if flag else 'No')




活动打卡代码 AcWing 851. spfa求最短路

皓首不倦
6小时前
'''
SPFA算法,解带负权边的有向图和不带负权边的无向图的单源
最短路问题
'''
from collections import deque

class SPFA:

    # start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
    def __init__(self, start_node, edges, is_directed):
        self.edges = edges[::]
        self.start_node = start_node
        self.is_directed = is_directed

    # 获取最短路径长度的列表[(节点1,长度1), (节点2, 长度2) .....]
    def getMinPathLen(self):
        return self.getMinInfo(False)

    # 获取所有最短路径列表[(节点1, 长度1, 路径节点列表1), (节点2, 长度2, 路径节点列表2)]
    def getMinPath(self):
        return self.getMinInfo(True)

    def getMinInfo(self, get_path):
        link = {}
        pre = {}                    # pre[x]表示以节点x结尾的最短路径的前驱节点
        dis, dis_tmp = {}, {}       # 起点到终点的最短距离

        for a, b, w in self.edges:
            if a not in dis:
                dis[a] = 0 if a == self.start_node else 0x7fffffff
            if b not in dis:
                dis[b] = 0 if b == self.start_node else 0x7fffffff

            if not self.is_directed:
                # 无向图检查是否有负边
                if w < 0:
                    return None

                if a not in link:
                    link[a] = []
                if b not in link:
                    link[b] = []

                link[a].append((b, w))
                link[b].append((a, w))

            else:
                if a not in link:
                    link[a] = []
                link[a].append((b, w))


        updated_nodes = deque()
        # 第一次迭代之前,所有节点的距离都默认是上一轮迭代更新变小的
        for node in link:
            updated_nodes.append(node)

        # 进行V次迭代,第V次检查是否是无解情况
        iter_times = 0
        while iter_times < len(dis):
            # 所有边进行松弛操作
            update_flag = False

            for node in dis:
                dis_tmp[node] = dis[node]

            # 利用上一轮迭代距离变小的点进行松弛操作
            node_num = len(updated_nodes)
            update_set = set()
            for _ in range(node_num):
                a = updated_nodes.popleft()
                if a not in link:
                    continue

                for b, w in link[a]:
                    new_dis = 0x7fffffff if dis[a] == 0x7fffffff else dis[a] + w
                    if new_dis < dis_tmp[b]:
                        dis_tmp[b] = new_dis
                        pre[b] = a
                        update_flag = True

                        if b not in update_set:
                            update_set.add(b)
                            updated_nodes.append(b)

            dis, dis_tmp = dis_tmp, dis
            iter_times += 1

            if iter_times == len(dis):
                if update_flag:
                    return None

            if not update_flag:
                break

        # 生成路径函数
        def __getPath(end_node):
            stack = []
            node = end_node
            while True:
                stack.append(node)
                if node not in pre:
                    break
                node = pre[node]
            return stack[::-1]

        return [[node, dis[node], __getPath(node)] for node in dis] if get_path else [[node, dis[node]] for node in dis]

n, m = map(int, input().split())
edges = {}
for _ in range(m):
    a, b, w = map(int, input().split())
    if (a, b) not in edges:
        edges[(a, b)] = w
    else:
        edges[(a, b)] = min(edges[(a, b)], w)

edges = [(a, b, w) for (a, b), w in edges.items()]
algo = SPFA(1, edges, is_directed=True)
ans = algo.getMinPathLen()
for k, v in ans:
    if k == n:
        print(v if v != 0x7fffffff else 'impossible')
        break



皓首不倦
6小时前


'''
SPFA算法,解带负权边的有向图和不带负权边的无向图的单源
最短路问题
'''
from collections import deque

class SPFA:

    # start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
    def __init__(self, start_node, edges, is_directed):
        self.edges = edges[::]
        self.start_node = start_node
        self.is_directed = is_directed

    # 获取最短路径长度的列表[(节点1,长度1), (节点2, 长度2) .....]
    def getMinPathLen(self):
        return self.getMinInfo(False)

    # 获取所有最短路径列表[(节点1, 长度1, 路径节点列表1), (节点2, 长度2, 路径节点列表2)]
    def getMinPath(self):
        return self.getMinInfo(True)

    def getMinInfo(self, get_path):
        link = {}
        pre = {}                    # pre[x]表示以节点x结尾的最短路径的前驱节点
        dis, dis_tmp = {}, {}       # 起点到终点的最短距离

        for a, b, w in self.edges:
            if a not in dis:
                dis[a] = 0 if a == self.start_node else 0x7fffffff
            if b not in dis:
                dis[b] = 0 if b == self.start_node else 0x7fffffff

            if not self.is_directed:
                # 无向图检查是否有负边
                if w < 0:
                    return None

                if a not in link:
                    link[a] = []
                if b not in link:
                    link[b] = []

                link[a].append((b, w))
                link[b].append((a, w))

            else:
                if a not in link:
                    link[a] = []
                link[a].append((b, w))


        updated_nodes = deque()
        # 第一次迭代之前,所有节点的距离都默认是上一轮迭代更新变小的
        for node in link:
            updated_nodes.append(node)

        # 进行V次迭代,第V次检查是否是无解情况
        iter_times = 0
        while iter_times < len(dis):
            # 所有边进行松弛操作
            update_flag = False

            for node in dis:
                dis_tmp[node] = dis[node]

            # 利用上一轮迭代距离变小的点进行松弛操作
            node_num = len(updated_nodes)
            update_set = set()
            for _ in range(node_num):
                a = updated_nodes.popleft()
                if a not in link:
                    continue

                for b, w in link[a]:
                    new_dis = 0x7fffffff if dis[a] == 0x7fffffff else dis[a] + w
                    if new_dis < dis_tmp[b]:
                        dis_tmp[b] = new_dis
                        pre[b] = a
                        update_flag = True

                        if b not in update_set:
                            update_set.add(b)
                            updated_nodes.append(b)

            dis, dis_tmp = dis_tmp, dis
            iter_times += 1

            if iter_times == len(dis):
                if update_flag:
                    return None

            if not update_flag:
                break

        # 生成路径函数
        def __getPath(end_node):
            stack = []
            node = end_node
            while True:
                stack.append(node)
                if node not in pre:
                    break
                node = pre[node]
            return stack[::-1]

        return [[node, dis[node], __getPath(node)] for node in dis] if get_path else [[node, dis[node]] for node in dis]

n, m = map(int, input().split())
edges = {}
for _ in range(m):
    a, b, w = map(int, input().split())
    if (a, b) not in edges:
        edges[(a, b)] = w
    else:
        edges[(a, b)] = min(edges[(a, b)], w)

edges = [(a, b, w) for (a, b), w in edges.items()]
algo = SPFA(1, edges, is_directed=True)
ans = algo.getMinPathLen()
for k, v in ans:
    if k == n:
        print(v if v != 0x7fffffff else 'impossible')
        break






皓首不倦
7小时前
'''
Bellman-Ford算法,解带负权边的有向图和不带负权边的无向图的单源
最短路问题
'''


class BellmanFord:

    # start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
    def __init__(self, start_node, edges, is_directed, K):
        self.edges = edges[::]
        self.start_node = start_node
        self.is_directed = is_directed
        self.K = K

    # 获取最短路径长度的列表[(节点1,长度1), (节点2, 长度2) .....]
    def getMinPathLen(self):
        return self.getMinInfo(False)

    # 获取所有最短路径列表[(节点1, 长度1, 路径节点列表1), (节点2, 长度2, 路径节点列表2)]
    def getMinPath(self):
        return self.getMinInfo(True)

    def getMinInfo(self, get_path):
        link = {}
        pre = {}                    # pre[x]表示以节点x结尾的最短路径的前驱节点
        dis, dis_tmp = {}, {}       # 起点到终点的最短距离

        for a, b, w in self.edges:
            if a not in dis:
                dis[a] = 0 if a == self.start_node else 0x7fffffff
            if b not in dis:
                dis[b] = 0 if b == self.start_node else 0x7fffffff

            if not self.is_directed:
                # 无向图检查是否有负边
                if w < 0:
                    return None

                if a not in link:
                    link[a] = []
                if b not in link:
                    link[b] = []

                link[a].append((b, w))
                link[b].append((a, w))

            else:
                if a not in link:
                    link[a] = []
                link[a].append((b, w))

        # 进行V次迭代,第V次检查是否是无解情况
        iter_times = 0
        while iter_times < self.K:
            # 所有边进行松弛操作
            update_flag = False

            for node in dis:
                dis_tmp[node] = dis[node]

            for a in link:
                for b, w in link[a]:
                    new_dis = 0x7fffffff if dis[a] == 0x7fffffff else dis[a] + w
                    if new_dis < dis_tmp[b]:
                        dis_tmp[b] = new_dis
                        pre[b] = a
                        update_flag = True

            dis, dis_tmp = dis_tmp, dis
            iter_times += 1

            if not update_flag:
                break

        # 生成路径函数
        def __getPath(end_node):
            stack = []
            node = end_node
            while True:
                stack.append(node)
                if node not in pre:
                    break
                node = pre[node]
            return stack[::-1]

        return [[node, dis[node], __getPath(node)] for node in dis] if get_path else [[node, dis[node]] for node in dis]

n, m, k = map(int, input().split())
edges = {}
for _ in range(m):
    a, b, w = map(int, input().split())
    if (a, b) not in edges:
        edges[(a, b)] = w
    else:
        edges[(a, b)] = min(edges[(a, b)], w)

edges = [(a, b, w) for (a, b), w in edges.items()]
algo = BellmanFord(1, edges, is_directed=True, K=k)
ans = algo.getMinPathLen()
for k, v in ans:
    if k == n:
        print(v if v != 0x7fffffff else 'impossible')
        break




皓首不倦
7小时前


'''
Bellman-Ford算法,解带负权边的有向图和不带负权边的无向图的单源
最短路问题
'''


class BellmanFord:

    # start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
    def __init__(self, start_node, edges, is_directed, K):
        self.edges = edges[::]
        self.start_node = start_node
        self.is_directed = is_directed
        self.K = K

    # 获取最短路径长度的列表[(节点1,长度1), (节点2, 长度2) .....]
    def getMinPathLen(self):
        return self.getMinInfo(False)

    # 获取所有最短路径列表[(节点1, 长度1, 路径节点列表1), (节点2, 长度2, 路径节点列表2)]
    def getMinPath(self):
        return self.getMinInfo(True)

    def getMinInfo(self, get_path):
        link = {}
        pre = {}                    # pre[x]表示以节点x结尾的最短路径的前驱节点
        dis, dis_tmp = {}, {}       # 起点到终点的最短距离

        for a, b, w in self.edges:
            if a not in dis:
                dis[a] = 0 if a == self.start_node else 0x7fffffff
            if b not in dis:
                dis[b] = 0 if b == self.start_node else 0x7fffffff

            if not self.is_directed:
                # 无向图检查是否有负边
                if w < 0:
                    return None

                if a not in link:
                    link[a] = []
                if b not in link:
                    link[b] = []

                link[a].append((b, w))
                link[b].append((a, w))

            else:
                if a not in link:
                    link[a] = []
                link[a].append((b, w))

        # 进行V次迭代,第V次检查是否是无解情况
        iter_times = 0
        while iter_times < self.K:
            # 所有边进行松弛操作
            update_flag = False

            for node in dis:
                dis_tmp[node] = dis[node]

            for a in link:
                for b, w in link[a]:
                    new_dis = 0x7fffffff if dis[a] == 0x7fffffff else dis[a] + w
                    if new_dis < dis_tmp[b]:
                        dis_tmp[b] = new_dis
                        pre[b] = a
                        update_flag = True

            dis, dis_tmp = dis_tmp, dis
            iter_times += 1

            if not update_flag:
                break

        # 生成路径函数
        def __getPath(end_node):
            stack = []
            node = end_node
            while True:
                stack.append(node)
                if node not in pre:
                    break
                node = pre[node]
            return stack[::-1]

        return [[node, dis[node], __getPath(node)] for node in dis] if get_path else [[node, dis[node]] for node in dis]

n, m, k = map(int, input().split())
edges = {}
for _ in range(m):
    a, b, w = map(int, input().split())
    if (a, b) not in edges:
        edges[(a, b)] = w
    else:
        edges[(a, b)] = min(edges[(a, b)], w)

edges = [(a, b, w) for (a, b), w in edges.items()]
algo = BellmanFord(1, edges, is_directed=True, K=k)
ans = algo.getMinPathLen()
for k, v in ans:
    if k == n:
        print(v if v != 0x7fffffff else 'impossible')
        break