schinapi

2.2万

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
def Floyd():
# k = i = j = 1 # !!!大错误，应该将每个遍历变量的初始化放在循环内，而不是循环外
# while k<=n:
#     while i<=n:
#         while j<=n:
#             dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
#             j+= 1
#         i+= 1
#     k+= 1
for k in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

if __name__ == '__main__':
n, m, q = map(int, input().split())
N = 210
# dist存储i到j的最短距离
dist = [[float('inf')]*N for i in range(N)]
for i in range(N):
for j in range(N):
if i == j: dist[i][j] = 0
for i in range(1, m+1):
x, y, z = map(int, input().split())
dist[x][y] = min(dist[x][y], z)
Floyd()
for i in range(q):
x, y = map(int, input().split())
print('impossible' if dist[x][y] == float('inf') else dist[x][y])


//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
def Prim():
"""
返回最小生成树的最短距离
遍历n个点放入集合，每次更新集合外的点到集合的最短距离
"""
res = 0
for i in range(n):
t = -1
# 找到距离集合最近的点
for j in range(1, n+1):
if not st[j] and (t == -1 or dist[t]>dist[j]): t = j
# 当集合最近的点不连通时，失败
if i and dist[t] == float('inf'): return 'impossible'
# 将最近点放入集合
st[t] = True
# 如果不是第一个点，将结果加上最短距离
if i: res += dist[t]
# 更新集合外所有点到集合的距离，注意要先计算结果，否则可能负环会把距离更新掉
for j in range(1, n+1): dist[j] = min(dist[j], g[t][j])
return res
if __name__ == '__main__':
n, m = map(int, input().split())
N = 510
# 存储所有的边
g = [[float('inf')]*N for i in range(N)]
# 存储集合外的点到集合的最短距离
dist = [float('inf')]*N
st = [False]*N
for i in range(m):
a, b, c = map(int, input().split())
g[a][b] = g[b][a] = min(g[a][b], c)
print(Prim())


//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
import heapq
def spfa_ring():
"""
寻找负权回路
"""
cont = [0]*N    #存储跟新后节点的最小距离的边数，可以不用初始化
heap = []
# 将所有节点入队，防止负权回路存在于非连通域
for i in range(1,n+1):
heapq.heappush(heap, i)
while len(heap):
t = heapq.heappop(heap)
st[t] = False
i = h[t]
while i!= -1:
node = e[i]
if dist[node] > dist[t] + w[i]:
dist[node] = dist[t] + w[i]
cont[node] = cont[t] + 1
# 根据抽屉原理，当节点的最短距离大于等于n时，存在负权回路
if cont[node] >= n: return True
# 将有限序列中不存在的节点推入
if not st[node]:
heapq.heappush(heap, node)
st[node] = True
i = ne[i]
return False
if __name__ == '__main__':
n, m = map(int, input().split())
N = 100010
h, ne, e = [[-1]*N for i in range(3)]
idx = 0
# ！！！注意：这里绝对不同用float("inf"),因为在比较dist距离时，dist[t]+w还是==float("inf")，因此不能更新距离
w, dist = [[0]*N for i in range(2)]
dist[1] = 0
st = [True]*N
for i in range(m):
a, b, c = map(int, input().split())
e[idx] = b
ne[idx] = h[a]
h[a] = idx
w[idx] = c
idx += 1
print('Yes' if spfa_ring() else 'No')



//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
import heapq
def spfa():
"""
堆优化的bellman_ford算法，在不存在负权回路时可以适用。
复杂度最好为O（n),最坏为O（nm）
只有节点有更新时，遍历其每一条边
"""
heap = []
heapq.heappush(heap, 1)
st[1] = True
while len(heap):
t = heapq.heappop(heap)
st[t] = False
i = h[t]
while i!= -1:
node = e[i]
if dist[node] > dist[t] + w[i]:
dist[node] = dist[t] + w[i]
# 将有限序列中不存在的节点推入
if not st[node]:
heapq.heappush(heap, node)
st[node] = True
i = ne[i]
return 'impossible' if dist[n] == float('inf') else dist[n]
if __name__ == '__main__':
n, m = map(int, input().split())
N = 100010
h, ne, e = [[-1]*N for i in range(3)]
idx = 0
w, dist = [[float('inf')]*N for i in range(2)]
dist[1] = 0
st = [False]*N
for i in range(m):
a, b, c = map(int, input().split())
e[idx] = b
ne[idx] = h[a]
h[a] = idx
w[idx] = c
idx += 1
print(spfa())



//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
def Bellman_ford():
只有上一次迭代中松驰过的点才能参加下一次迭代的松弛操作
for i in range(k):
# 有边数限制的最短路时，一定要进行备份，更新时和上一次迭代的结果相比较，防止遍历时出现串联问题
# 如果不使用备份数组，允许串联式更新，那么第k次更新的最短路上边的数量至少是 k
# 限制这个点只能用上一个结点迭代的结果
backup = dist[::]
for j in range(m):
a, b, w = edges[j]
# 遍历所有的边，每次迭代最少更新一个点的最短距离。
# 若第n此迭代仍能更新，根据抽屉原理说明至少存在一条负权回路，可以用来判断负权边
if dist[b]>backup[a] + w: dist[b] = backup[a] + w
return 'impossible' if dist[n] == float('inf') else dist[n]

if __name__ == '__main__':
n, m, k = map(int, input().split())
# 存储图中所有的边
edges = [tuple(map(int, input().split())) for i in range(m)]
dist = [float('inf')]*(n+10)
dist[1] = 0
print(Bellman_ford())


//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
import heapq

def dijstra_heap():
# 初始化1到起点的距离为0，并将0，1 压入队列作为循环起点
dist[1] = 0
heapq.heappush(heap, (0, 1))
while len(heap):
t = heapq.heappop(heap)
node = t[1]
dis = t[0]
# 若节点到起点的最小距离未确定，那么更新其所有邻接点的距离
if st[node]: continue
st[node] = True
j = h[node]
while j != -1:
i = e[j]
# 如果邻接点的距离大于节点的距离+边的长度，那么更新这个距离，并压入队列
if dis + w[j] < dist[i]:
dist[i] = dis + w[j]
heapq.heappush(heap, (dist[i], i))
j = ne[j]
return -1 if dist[n] == float('inf') else dist[n]

if __name__ == '__main__':
# 根据n,m的范围确定时稀疏图，用邻接表存储
n, m = map(int, input().split())
N = 150010
h, e, ne = [-1] * N, [-1] * N, [-1] * N
# w存储边的长度
w = [float('inf')] * N
idx = 0
st = [False] * N
dist = [float('inf')] * N
# heap优先队列存储节点和其到起点的距离
heap = []
for i in range(m):
a, b, c = map(int, input().split())
e[idx] = b
ne[idx] = h[a]
h[a] = idx
w[idx] = c
idx += 1
print(dijstra_heap())



//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
def dijstra():
"""
遍历n个节点，找到其中距离起点最短的点，然后更新所有点的距离。时间复杂度O（n**2+m)
"""
for i in range(n):
# t作为每次寻找最小距离点的起始位置。-1而不是0，我的理解是，为了防止节点的下标从0开始，-1比较方便适用2种情况
t = -1
for j in range(1, n+1):
if st[j] == 0 and (t == -1 or dist[j]<dist[t]):
t = j
st[t]  = 1
# 更新所有点的距离，取当前点到t的距离和t到起点距离和，与起点到当前点距离的最小值
for k in range(1, n+1):
dist[k] = min(dist[k], dist[t] + g[t][k])
if dist[n] == float('inf'): return -1
else: return dist[n]

if __name__ == '__main__':
n, m = map(int, input().split())
N  = 510
# 稠密图用邻接矩阵存储，因为可能有重边，初始值设为无穷大
g = [[float('inf')]*N for i in range(N)]
# 存储节点的最短路径是否已经确定
st = [0]*N
# 存储每个节点到起点的最短路径
dist = [float('inf')]*N
# 设1为起点
dist[1] = 0
for i in range(m):
a, b, c = map(int, input().split())
# 若存在重边，取较小的边
g[a][b] = min(g[a][b], c)
print(dijstra())


//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#  拓扑排序答案不唯一
# 有向无环图至少存在一个拓扑序列
# 根据每个节点的入度来判断是否入队

def topsort():
"""
返回是否存在拓扑排序
"""
hh = 0
tt = -1
for i in range(1, n + 1):
# 入度为0的点入队，作为起点
if d[i] == 0:
tt += 1
q[tt] = i
while hh <= tt:
t = q[hh]
hh += 1
i = h[t]
# 遍历队首的每一个邻接点
while i != -1:
j = e[i]
# 每访问一个元素，其入度减一
d[j] -= 1
# 若入度为0则入队
if d[j] == 0:
tt += 1
q[tt] = j
i = ne[i]
# 若所有元素都入队，那么存在拓扑
return tt == n - 1

def ins(a, b):
"""
邻接表
"""
global idx
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx += 1

if __name__ == '__main__':
n, m = map(int, input().split())
N = 100010
e = [-1] * N
h = [-1] * N
ne = [-1] * N
idx = 0
q = [0] * n
d = [0] * N
for i in range(m):
a, b = map(int, input().split())
ins(a, b)
d[b] += 1      # 记录每个点的入度
if topsort():
print(' '.join(map(str, q)))
else:
print('-1')



//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
def dfs(x):
"""
x的子树中点的数量
"""
global ans      # 存储重心的最大节点数，即最大点数的最小值
st[x] = True       # 标注当前点已经被搜索过
su = 1  #存储以x为根的节点数，包括x
res = 0 #存储删除掉节点x后，剩余连通域的最大节点数
i = h[x]
while i != -1: # 访问当前x的第一个邻接点，如果其存在
j = e[i]       # 第一个邻接点的图的编号
if not st[j]:   # 如果邻接点未被访问过，那么对其进行递归
s = dfs(j)
res = max(res, s)
su += s
i = ne[i]    # 访问当前x的下一个邻接点，如果其存在
res = max(res, n - su)
ans = min(res, ans)
return su

def insert(x, y):
"""
将y节点插入单链表，父节点时x
"""
global idx
e[idx] = y
ne[idx] = h[x]
h[x] = idx
idx += 1

if __name__ == '__main__':
n = int(input().strip())
N = 10010
h = [-1] * N    # 存储每个点的单链表的头节点下标（e）,也就是第一个邻接点，链表中边的数量和图中边的数量相等，-1表示尾节点
e = [0] * N * 2 #存储节点在图中的编号
ne = [-1] * N * 2 # 存储邻接点的下一个邻接点的下标（e）
idx = 0          # 链表中的新节点编号
st = [False] * N
ans = N
for i in range(n - 1):
x, y = map(int, input().split())
# 单向图表示无向图
insert(x, y)
insert(y, x)
dfs(1)
print(ans)



//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
def bfs():
"""
逐层遍历图中所有节点
"""
q = [0] * N
q[0] = 1         # 队列存储对应编号
hh = 0
tt = 0
d = [-1] * N     # 存储对应编号和1之间的距离，初始点1的距离为0
d[1] = 0
while hh <= tt:   #队列不为空时，从1开始逐层遍历
t = q[hh]      # 队头出队
hh += 1
i = h[t]
while i != -1:  # 遍历队首的所有邻接点
j = e[i]
if d[j] == -1:   # 判断当前点是否被访问，未被访问则入队
tt += 1
q[tt] = j
d[j] = d[t] + 1  # 刚入队的距离等于正在被访问的队首距离+1，
i = ne[i]  # 前往下一个邻接点
return d[n]      # 遍历图中所有点后打印n的距离

def ins(a, b):
"""
邻接表
"""
global idx
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx += 1

if __name__ == '__main__':
N = 10010
M = 2 * N
e = [-1] * M
h = [-1] * N
idx = 0
ne = [0] * M
n, m = map(int, input().split())
for i in range(m):
a, b = map(int, input().split())
ins(a, b)
print(bfs())