【阿良的算法之路】图论最短路算法模板

图论总览🍉

---

最短路问题无非是求一张地图中一个点a到另一个点b最短的路径，

        对于单源最短路，我们只需要求点1（第一个点）到其他所有点的最短路径；对于一个朴素的图（没有重边，也没有负环，边的权重也不是负数）的情况下：我们使用堆优化的dirjkstra单源最短路径算法是最合适的。对于非朴素的图，我们需要使用Spfa单源最短路径算法。

        对于多源最短路，我们求的确实每一个点到其他所有点的最短路径。多源最短路都不考虑朴素的图，也就是有重边，也有负环，边的权重也是负数的情况，如果限制了最多只能经过k个点，那么我们使用Bellman-Ford多源最短路算法，不然使用Floya多源最短路算法。

---

【模板】dirjkstra单源最短路径👑

参考题目🍉

题目描述🎈

给定一个 n 个点，m 条有向边的带非负权图，请你计算从 s 出发，到每个点的距离。

数据保证你能从 s 出发到任意点。

输入格式🎈

第一行为三个正整数 n, m, s。 第二行起 m 行，每行三个非负整数 u_i, v_i, w_i，表示从 u_i 到 v_i 有一条权值为 w_i 的有向边。

输出格式🎈

输出一行 n 个空格分隔的非负整数，表示 s 到每个点的距离。

————————————————

'''
# #AC Code（dirjkstra单源最短路径)# #
'''
import heapq
from collections import defaultdict
# 核心代码
def dirjkstra():
    # 各节点到start的最短距离
    dirs = [float('inf')] * (n + 1)
    dirs[start] = 0
 
    # 已用节点，比set还快20% 所有没有释放False
    seen = [False] * (n + 1)
 
    pq = []
    heapq.heappush(pq, (0, start))
 
    # BFS
    while pq:
        # 获取
        _, u = heapq.heappop(pq)
        
        # 该节点是否用过
        if seen[u]:
            continue
        else:
            seen[u] = True
 
        # 找到邻接节点
        nodeList = graph[u]
        for v, w in nodeList:
            t = dirs[u] + w
            if t < dirs[v]:
                dirs[v] = t
                # 如果该邻接节点没有访问过才把该最短边加进去
                if not seen[v]:
                    heapq.heappush(pq, (t, v))
                
    if dirs[-1] == float('inf'):
        return -1
    else:
        return dirs[-1]
    
# 输入
n, m = map(int, input().split())
 
# 初始化
start = 1
 
# 建图
graph = defaultdict(list)
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v,w))
 
answer = dirjkstra()
print(answer)

【模板】Spfa求最短路👑

参考题目🍉

        给定一个n 个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。请你求出1号点到n 号点的最短距离，如果无法从1号点走到n号点，则输出impossible 。数据保证不存在负权回路。

输入格式：🎈

        第一行包含整数n和m。接下来m行每行包含三个整数a, y,z，表示存在一条从点α到点g的有向边，边长为z。

输出格式：🎈

        输出一个整数，表示1号点到n号点的最短距离。如果路径不存在，则输出impossible。

数据范围：🎈

1≤n, m≤10**5,

图中涉及边长绝对值不超过10000。

输入样例：🎈

3 3
1 2 5
2 3 -3
1 3 4

输出样例：🎈

2

————————————————

'''
# #AC Code（Spfa单源最短路 )# #
NOTE：队列存储距离有更新的点。
'''
# 队列存储距离有更新的点
def spfa():
    dirs = [float('inf')] * (n + 1) # 存储到1节点的最短距离
    dirs[1] = 0             
                            
    seen = [False] * (n + 1)    # 该节点是否在队列中
    
    q = [1]
    while len(q):
        u = q.pop(0)
        seen[u] = False
        
        for v, w in g[u]:
            if dirs[u] + w < dirs[v]:
                dirs[v] = dirs[u] + w
                # 如果该邻接节点没有访问过才把该点加进去
                if not seen[v]:
                    q.append(v)
                    seen[v] = True
                    
    if dirs[-1] == float('inf'):
        return 'impossible'
    else:
        return dirs[-1]
    
# 建边
n, m = map(int, input().split())
g = {x: [] for x in range(1, n + 1)}
for _ in range(m):
    a, b, w = map(int, input().split())
    g[a].append((b, w))
 
ans = spfa()
print(ans)

【模板】Spfa判断负环👑

参考题目🍉

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。

请你判断图中是否存在负权回路。

输入格式：🎈

第一行包含整数n和m。

接下来m行每行包含三个整数x, y, z, 表示存在一条从点x到点y的有向边，边长为z。

输出格式：🎈

如果图中存在负权回路，则输出Yes，否则输出No。

数据范围：🎈

输入样例：🎈

3 3
1 2 -1
2 3 4
3 1 -4

输出样例：🎈

Yes

————————————————

'''
# #AC Code（Spfa判断负环 )# #
'''
from collections import deque, defaultdict
def spfa():
    dirs = [0] * (n + 1) # 表示的是1到s的最短距离           
                            
    seen = [False] * (n + 1)    # 该节点是否走过
 
    cnt = [0] * (n + 1) #  表示的是当前最短路的边的数量
    
    q = deque([x for x in range(1, n + 1)])
    
    while len(q):
        u = q.popleft()
 
        seen[u] = False
        
        for v, w in g[u]:
            t = dirs[u] + w
            if t < dirs[v]:
                dirs[v] = t
                
                cnt[v] = cnt[u] + 1
                if cnt[v] >= n:
                    return True
    
                if not seen[v]:
                    q.append(v)
                    seen[v] = True
    return False
 
# 建图模板
n, m = map(int, input().split())
g = defaultdict(list)
for _ in range(m):
    u, v, w = map(int, input().split())
    g[u].append((v, w))
 
 
print("Yes" if spfa() else "No")

【模板】Floya（不限制经过多少条边）👑

 ————————————————

#### ####### #########################
### floyd多源最短路不限制经过多少条边 ###
#### ####### ##########################
def floyd():
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return 
 
n, m, k = map(int, input().split())#输入
dp = [[float('inf')] * (n + 1) for _ in range(n + 1)]#开dp数组
#   d[i][j] 结点i到结点j的最短距离
for i in range(1, n + 1):   # 结点i到自己为0
    dp[i][i] = 0
 
for _ in range(m):  # m 条有向边 
    u, v, w = map(int, input().split())
    dp[u][v] = min(dp[u][v], w) # 连边中u可能等于v此时选择最小的
    # 解决重边和自环 都选最小的
 
floyd()
 
for _ in range(k):
    u, v = map(int, input().split())
    print('impossible' if dp[u][v]==float('inf') else dp[u][v])

【模板】Bellman-Ford多源最短路👑

参考题目🍉

给定一个 n 个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

注意：图中可能 存在负权回路 。

输入格式🎈

第一行包含三个整数 n,m,k。

接下来 mm 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式🎈

输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径，则输出 impossible。

数据范围🎈

1≤n,k≤5001≤n,k≤500,
1≤m≤100001≤m≤10000,
任意边长的绝对值不超过 1000010000。

————————————————

'''
# #AC Code（BF多源最短路)# #
NOTE：从 1 号点到 n 号点的最多经过 k 条边的最短距离。
# new_list = list ！！当list的值改变了new_list也会随着改变
# 正确做法： new_list = list(list)
'''
n, m, k = map(int, input().split())
edgeList = [tuple(map(int, input().split())) for _ in range(m)]
dirs = [float('inf') for _ in range(n + 1)]
dirs[1] = 0
for _ in range(k):
    back = list(dirs)
    for u, v, w in edgeList:
        dirs[v] = min(dirs[v], back[u] + w)
if dirs[-1] == float('inf'):
    print('impossible')
else:
    print(dirs[-1])

【模板】Kruskal最小生成树（最短的一个环路）👑

参考题目🍉

给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。

给定一张边带权的无向图=(V,E)，其中V表示图中点的集合，E表示图中边的集合，n=|V\，m =|E。

由V中的全部n个顶点和E中n―1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图的最小生成树。

输入格式：🎈

第一行包含两个整数n和m。

接下来m行，每行包含三个整数u, v, ww，表示点u和点v之间存在一条权值为w的边。

输出格式：🎈

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出impossible 。

数据范围：🎈

输入样例：🎈

4 5
1 2 1
1 3 2
1 4 3
2 3 2 
3 4 4

输出样例：🎈

6

'''
# #AC Code（Kruskal最小生成树)# #
NOTE：最短的一个环路。
'''
from collections import defaultdict, deque
 
def find(x):
    if not p[x] == x:
        p[x] = find(p[x])
    return p[x]
    
n, m = map(int, input().split())
p = [_ for _ in range(n + 1)]
g = []
for _ in range(m):
    g.append(tuple(map(int, input().split())))
g.sort(key=lambda x:x[2])
 
cnt = 0
res = 0
for u, v, w in g:
    eu = find(u)
    ev = find(v)
    if eu == ev: continue
    p[ev] = eu
    res += w
    cnt += 1
 
print('impossible') if not cnt == n - 1 else print(res)