头像

皓首不倦


访客:2496

在线 


活动打卡代码 AcWing 341. 最优贸易

皓首不倦
6小时前
'''
题目要求的答案是从1走到N的所有可能的路径上,靠后的最大值和靠前的最小值之间的差值的最大值,先用DP
的思维分析问题,所有路径方案可以用分割点k进行区分,表示买入发生在1到K的路径上, 卖出发生在K到N的
路径上,dp(k)表示从1到k所有可能路径上出现的最小值,dp(k) = min{dp(s1), dp(s2)....dp(sn), w[k]}
其中sx是能走到k的上一个点,w[k]是k这个点的权值,但是这个DP显然可能有环,常规的DP递推会死循环,
所以只能转成最短路来求解,1到x距离就定义为dp(x), dp(k) = min{dp(s1), dp(s2)....dp(sn), w[k]}
就是距离的计算公式,最多只有N个点,根据SPFA的思维,从起点走到K最多走N-1次,距离最小值一定得到了,同样的
把所有点反向,求N到所有点的最长路径,就可以得到任意一个点K走到N的所有经过节点中的最大值,正反两次
SPFA就可以求出任何一点K,从1走到K的节点最小值和K走到N的节点最大值,最后枚举所有的K,用对应的最大值
减去最小值,取其中最大的差值即可
'''
from collections import deque

n, m = map(int, input().split())
w = [0] + list(map(int, input().split()))

link = [[] for _ in range(n+1)]
link_rev = [[] for _ in range(n+1)]
for i in range(m):
    a, b, type = map(int, input().split())
    if type == 1:
        link[a].append(b)
        link_rev[b].append(a)
    else:
        link[a].append(b)
        link[b].append(a)
        link_rev[a].append(b)
        link_rev[b].append(a)


def spfa_min():
    global w
    que = deque()
    que.append(1)
    dis = [0x7fffffff] * (n+1)
    dis[1] = w[1]
    in_que = [0] * (n + 1)
    in_que[1] = 1

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

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

            for b in link[a]:
                new_dis = min(dis[a], w[b])
                if new_dis < dis[b]:
                    dis[b] = new_dis
                    update_flag = True

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

        iter_times += 1

        if iter_times == n:
            if update_flag:
                return None

        if not update_flag:
            break

    return [[node, dis[node]] for node in range(1, n + 1)]

def spfa_max():
    global w
    que = deque()
    que.append(n)
    dis = [-0x7fffffff] * (n+1)
    dis[n] = w[n]
    in_que = [0] * (n + 1)
    in_que[n] = 1

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

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

            for b in link_rev[a]:
                new_dis = max(dis[a], w[b])
                if new_dis > dis[b]:
                    dis[b] = new_dis
                    update_flag = True

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

        iter_times += 1

        if iter_times == n:
            if update_flag:
                return None

        if not update_flag:
            break

    return [[node, dis[node]] for node in range(1, n + 1)]


min_dist = spfa_min()
max_dist = spfa_max()
# print(min_dist)
# print(max_dist)
ans = 0
for k in range(n):
    ans = max(ans, max_dist[k][1] - min_dist[k][1])
print(ans)



皓首不倦
6小时前


'''
题目要求的答案是从1走到N的所有可能的路径上,靠后的最大值和靠前的最小值之间的差值的最大值,先用DP
的思维分析问题,所有路径方案可以用分割点k进行区分,表示买入发生在1到K的路径上, 卖出发生在K到N的
路径上,dp(k)表示从1到k所有可能路径上出现的最小值,dp(k) = min{dp(s1), dp(s2)....dp(sn), w[k]}
其中sx是能走到k的上一个点,w[k]是k这个点的权值,但是这个DP显然可能有环,常规的DP递推会死循环,
所以只能转成最短路来求解,1到x距离就定义为dp(x), dp(k) = min{dp(s1), dp(s2)....dp(sn), w[k]}
就是距离的计算公式,最多只有N个点,根据SPFA的思维,从起点走到K最多走N-1次,距离最小值一定得到了,同样的
把所有点反向,求N到所有点的最长路径,就可以得到任意一个点K走到N的所有经过节点中的最大值,正反两次
SPFA就可以求出任何一点K,从1走到K的节点最小值和K走到N的节点最大值,最后枚举所有的K,用对应的最大值
减去最小值,取其中最大的差值即可
'''
from collections import deque

n, m = map(int, input().split())
w = [0] + list(map(int, input().split()))

link = [[] for _ in range(n+1)]
link_rev = [[] for _ in range(n+1)]
for i in range(m):
    a, b, type = map(int, input().split())
    if type == 1:
        link[a].append(b)
        link_rev[b].append(a)
    else:
        link[a].append(b)
        link[b].append(a)
        link_rev[a].append(b)
        link_rev[b].append(a)


def spfa_min():
    global w
    que = deque()
    que.append(1)
    dis = [0x7fffffff] * (n+1)
    dis[1] = w[1]
    in_que = [0] * (n + 1)
    in_que[1] = 1

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

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

            for b in link[a]:
                new_dis = min(dis[a], w[b])
                if new_dis < dis[b]:
                    dis[b] = new_dis
                    update_flag = True

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

        iter_times += 1

        if iter_times == n:
            if update_flag:
                return None

        if not update_flag:
            break

    return [[node, dis[node]] for node in range(1, n + 1)]

def spfa_max():
    global w
    que = deque()
    que.append(n)
    dis = [-0x7fffffff] * (n+1)
    dis[n] = w[n]
    in_que = [0] * (n + 1)
    in_que[n] = 1

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

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

            for b in link_rev[a]:
                new_dis = max(dis[a], w[b])
                if new_dis > dis[b]:
                    dis[b] = new_dis
                    update_flag = True

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

        iter_times += 1

        if iter_times == n:
            if update_flag:
                return None

        if not update_flag:
            break

    return [[node, dis[node]] for node in range(1, n + 1)]


min_dist = spfa_min()
max_dist = spfa_max()
# print(min_dist)
# print(max_dist)
ans = 0
for k in range(n):
    ans = max(ans, max_dist[k][1] - min_dist[k][1])
print(ans)




活动打卡代码 AcWing 342. 道路与航线

皓首不倦
22小时前
'''
将每一个无向边连起来的连通块看成一个大的点,大点之间用可能是负权的边连接起来,把S当做起点,
按照拓扑排序的结果对每一个连通的大点做单源最短路,当入度为0的连通块大点出队的时候,依赖于
拓扑序的性质,所有有有向边和这个连通块中的节点相连的其他节点的S开始的最短路长度是已经求出来的,
进行新一轮单源最短路时候,节点就是新的出队连通块中的节点,但是节点的初始距离不是常规的Dijkstra中的无穷大,
因为此时源点并不是新连通块中的节点,而是从始到终都是S点,所以节点的初始距离是
所有指向这个新连通块中节点的有向边的起点到S的最短距离再加上有向边权值的和的最小值
'''


from typing import List, Tuple
from queue import PriorityQueue
from collections import deque


class DijkStra:
    # start_node 是单源最短路起点 edges是边的三元组(节点1, 节点2, 边权重) nodes是所有节点的列表
    def __init__(self, start_node, edges: List[Tuple[int, int, int]], nodes: List[int], is_directed = False, node2init_dist = None):
        self.edges = edges
        self.nodes = nodes
        self.start_node = start_node
        self.is_directed = is_directed
        self.node2init_dist = node2init_dist

    def __init(self):
        edges = self.edges
        nodes = self.nodes
        start_node = self.start_node

        self.link = {node: {} for node in nodes}  # 邻接表
        self.start_node = start_node
        self.S = {}  # 已经确定最短路径长度的节点集合
        self.total_nodes_num = len(nodes)

        U = None
        if self.node2init_dist is None:
            U = {node: 0x7fffffff for node in nodes if node != start_node}  # 还未确定最短路径长度的节点集合
            U[start_node] = 0

            for a, b, edge_len in edges:
                self.link[a][b] = edge_len
                if not self.is_directed:
                    self.link[b][a] = edge_len

                if a == start_node:
                    U[b] = edge_len

                if not self.is_directed:
                    if b == start_node:
                        U[a] = edge_len
        else:
            U = self.node2init_dist
            for a, b, edge_len in edges:
                self.link[a][b] = edge_len
                if not self.is_directed:
                    self.link[b][a] = edge_len

        self.U_que = PriorityQueue()  # 维护U集合的小顶堆,堆里面的内容是(路径长度, 节点值)的二元组
        for k, v in U.items():
            self.U_que.put((v, k))


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

    def getMinInfo(self):
        self.__init()
        pre = {}  # 记录每个节点结尾的最短路径的前驱节点

        while len(self.S) != self.total_nodes_num:
            while True:
                min_edge_len, min_node = self.U_que.get_nowait()  # 从U中把当前路径长度最小的节点取出来
                if min_node not in self.S:
                    break

            self.S[min_node] = min_edge_len

            # 更新U集合中节点的距离
            for next in self.link[min_node]:
                if next not in self.S:
                    if next not in pre or min_edge_len + self.link[min_node][next] < self.S[pre[next]] + self.link[pre[next]][next]:
                        self.U_que.put_nowait((min_edge_len + self.link[min_node][next], next))
                        pre[next] = min_node

        return {k: v for k, v in self.S.items()}

'''
并查集实现
'''
class MergeSet:
    def __init__(self):
        self.m = {}
        self.__root_cnt = 0

    def getRoot(self, node):
        root = node
        buf = []
        while self.m[root] != root:
            buf.append(root)
            root = self.m[root]
        for node in buf:
            self.m[node] = root

        return root

    def merge(self, a, b):
        for node in [a, b]:
            if node not in self.m:
                self.m[node] = node
                self.__root_cnt += 1

        root1 = self.getRoot(a)
        root2 = self.getRoot(b)
        if root1 != root2:
            self.m[root1] = root2
            self.__root_cnt -= 1

    def isInSameSet(self, a, b):
        if a == b:
            return True

        for node in [a, b]:
            if node not in self.m:
                return False

        return self.getRoot(a) == self.getRoot(b)

    def getRootNum(self):
        return self.__root_cnt

    def getClusters(self):
        rec = {}
        for node in self.m:
            root = self.getRoot(node)
            if root not in rec:
                rec[root] = []
            rec[root].append(node)
        return [nodes for nodes in rec.values()]


N, m1, m2, S = map(int, input().split())
merge_set = MergeSet()
edges_no_direct = {}
edges_direct = {}
node2directed_ne = [[] for _ in range(N + 1)]
node2no_directed_ne = [[] for _ in range(N + 1)]

for node in range(1, N + 1):
    merge_set.merge(node, node)
for i in range(m1):
    a, b, w = map(int, input().split())
    merge_set.merge(a, b)

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

for (a, b), w in edges_no_direct.items():
    node2no_directed_ne[a].append((b, w))


for i in range(m2):
    a, b, w = map(int, input().split())
    if (a, b) not in edges_direct:
        edges_direct[(a, b)] = w
    else:
        edges_direct[(a, b)] = min(w, edges_direct[(a, b)])

for (a, b), w in edges_direct.items():
    node2directed_ne[a].append((b, w))


node2cluster = [0]*(N+1)  # 节点到团的编号
clusters = merge_set.getClusters()

for idx, cluster in enumerate(clusters):
    for node in cluster:
        node2cluster[node] = idx

cluster2degree = [0] * (N + 1)  # 每一个团的入度
for (a, b), w in edges_direct.items():
        cluster2degree[node2cluster[b]] += 1

# 先算出来起始团里面的最短路
ans = [0x7fffffff] * (N + 1)
ans[S] = 0

que = deque()
for i in range(len(clusters)):
    if cluster2degree[i] == 0:
        que.append(i)

while len(que) > 0:
    cur_cluster = que.popleft()

    init_dist = {}
    edges = []
    for node in clusters[cur_cluster]:
        for next_node, w in node2directed_ne[node]:
            next_cluster = node2cluster[next_node]
            cluster2degree[next_cluster] -= 1
            if cluster2degree[next_cluster] == 0:
                que.append(next_cluster)

        init_dist[node] = ans[node]
        for next, w in node2no_directed_ne[node]:
            edges.append((node, next, w))

    # 这里节点的初始距离不是默认的,需要手动用node2init_dist参数设置
    algo = DijkStra(None, edges, clusters[cur_cluster], is_directed=False, node2init_dist=init_dist)
    min_len = algo.getMinPathLen()
    for node, length in min_len.items():
        ans[node] = min(ans[node], length)
        for next_node, w in node2directed_ne[node]:
            ans[next_node] = min(ans[next_node], ans[node] + w)     # 更新后继节点的最短距离


for i in range(1, N + 1):
    if ans[i] >= 2047482830:
        print("NO PATH")
    else:
        print(ans[i])



皓首不倦
22小时前

'''
将每一个无向边连起来的连通块看成一个大的点,大点之间用可能是负权的边连接起来,把S当做起点,
按照拓扑排序的结果对每一个连通的大点做单源最短路,当入度为0的连通块大点出队的时候,依赖于
拓扑序的性质,所有有有向边和这个连通块中的节点相连的其他节点的S开始的最短路长度是已经求出来的,
进行新一轮单源最短路时候,节点就是新的出队连通块中的节点,但是节点的初始距离不是常规的Dijkstra中的无穷大,
因为此时源点并不是新连通块中的节点,而是从始到终都是S点,所以节点的初始距离是
所有指向这个新连通块中节点的有向边的起点到S的最短距离再加上有向边权值的和的最小值
'''


from typing import List, Tuple
from queue import PriorityQueue
from collections import deque


class DijkStra:
    # start_node 是单源最短路起点 edges是边的三元组(节点1, 节点2, 边权重) nodes是所有节点的列表
    def __init__(self, start_node, edges: List[Tuple[int, int, int]], nodes: List[int], is_directed = False, node2init_dist = None):
        self.edges = edges
        self.nodes = nodes
        self.start_node = start_node
        self.is_directed = is_directed
        self.node2init_dist = node2init_dist

    def __init(self):
        edges = self.edges
        nodes = self.nodes
        start_node = self.start_node

        self.link = {node: {} for node in nodes}  # 邻接表
        self.start_node = start_node
        self.S = {}  # 已经确定最短路径长度的节点集合
        self.total_nodes_num = len(nodes)

        U = None
        if self.node2init_dist is None:
            U = {node: 0x7fffffff for node in nodes if node != start_node}  # 还未确定最短路径长度的节点集合
            U[start_node] = 0

            for a, b, edge_len in edges:
                self.link[a][b] = edge_len
                if not self.is_directed:
                    self.link[b][a] = edge_len

                if a == start_node:
                    U[b] = edge_len

                if not self.is_directed:
                    if b == start_node:
                        U[a] = edge_len
        else:
            U = self.node2init_dist
            for a, b, edge_len in edges:
                self.link[a][b] = edge_len
                if not self.is_directed:
                    self.link[b][a] = edge_len

        self.U_que = PriorityQueue()  # 维护U集合的小顶堆,堆里面的内容是(路径长度, 节点值)的二元组
        for k, v in U.items():
            self.U_que.put((v, k))


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

    def getMinInfo(self):
        self.__init()
        pre = {}  # 记录每个节点结尾的最短路径的前驱节点

        while len(self.S) != self.total_nodes_num:
            while True:
                min_edge_len, min_node = self.U_que.get_nowait()  # 从U中把当前路径长度最小的节点取出来
                if min_node not in self.S:
                    break

            self.S[min_node] = min_edge_len

            # 更新U集合中节点的距离
            for next in self.link[min_node]:
                if next not in self.S:
                    if next not in pre or min_edge_len + self.link[min_node][next] < self.S[pre[next]] + self.link[pre[next]][next]:
                        self.U_que.put_nowait((min_edge_len + self.link[min_node][next], next))
                        pre[next] = min_node

        return {k: v for k, v in self.S.items()}

'''
并查集实现
'''
class MergeSet:
    def __init__(self):
        self.m = {}
        self.__root_cnt = 0

    def getRoot(self, node):
        root = node
        buf = []
        while self.m[root] != root:
            buf.append(root)
            root = self.m[root]
        for node in buf:
            self.m[node] = root

        return root

    def merge(self, a, b):
        for node in [a, b]:
            if node not in self.m:
                self.m[node] = node
                self.__root_cnt += 1

        root1 = self.getRoot(a)
        root2 = self.getRoot(b)
        if root1 != root2:
            self.m[root1] = root2
            self.__root_cnt -= 1

    def isInSameSet(self, a, b):
        if a == b:
            return True

        for node in [a, b]:
            if node not in self.m:
                return False

        return self.getRoot(a) == self.getRoot(b)

    def getRootNum(self):
        return self.__root_cnt

    def getClusters(self):
        rec = {}
        for node in self.m:
            root = self.getRoot(node)
            if root not in rec:
                rec[root] = []
            rec[root].append(node)
        return [nodes for nodes in rec.values()]


N, m1, m2, S = map(int, input().split())
merge_set = MergeSet()
edges_no_direct = {}
edges_direct = {}
node2directed_ne = [[] for _ in range(N + 1)]
node2no_directed_ne = [[] for _ in range(N + 1)]

for node in range(1, N + 1):
    merge_set.merge(node, node)
for i in range(m1):
    a, b, w = map(int, input().split())
    merge_set.merge(a, b)

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

for (a, b), w in edges_no_direct.items():
    node2no_directed_ne[a].append((b, w))


for i in range(m2):
    a, b, w = map(int, input().split())
    if (a, b) not in edges_direct:
        edges_direct[(a, b)] = w
    else:
        edges_direct[(a, b)] = min(w, edges_direct[(a, b)])

for (a, b), w in edges_direct.items():
    node2directed_ne[a].append((b, w))


node2cluster = [0]*(N+1)  # 节点到团的编号
clusters = merge_set.getClusters()

for idx, cluster in enumerate(clusters):
    for node in cluster:
        node2cluster[node] = idx

cluster2degree = [0] * (N + 1)  # 每一个团的入度
for (a, b), w in edges_direct.items():
        cluster2degree[node2cluster[b]] += 1

# 先算出来起始团里面的最短路
ans = [0x7fffffff] * (N + 1)
ans[S] = 0

que = deque()
for i in range(len(clusters)):
    if cluster2degree[i] == 0:
        que.append(i)

while len(que) > 0:
    cur_cluster = que.popleft()

    init_dist = {}
    edges = []
    for node in clusters[cur_cluster]:
        for next_node, w in node2directed_ne[node]:
            next_cluster = node2cluster[next_node]
            cluster2degree[next_cluster] -= 1
            if cluster2degree[next_cluster] == 0:
                que.append(next_cluster)

        init_dist[node] = ans[node]
        for next, w in node2no_directed_ne[node]:
            edges.append((node, next, w))

    # 这里节点的初始距离不是默认的,需要手动用node2init_dist参数设置
    algo = DijkStra(None, edges, clusters[cur_cluster], is_directed=False, node2init_dist=init_dist)
    min_len = algo.getMinPathLen()
    for node, length in min_len.items():
        ans[node] = min(ans[node], length)
        for next_node, w in node2directed_ne[node]:
            ans[next_node] = min(ans[next_node], ans[node] + w)     # 更新后继节点的最短距离


for i in range(1, N + 1):
    if ans[i] >= 2047482830:
        print("NO PATH")
    else:
        print(ans[i])




活动打卡代码 AcWing 340. 通信线路


'''
题目的意思是在无向图中求1到N的所有可能路径中第K+1大的边的最小值是多少

可以进行二分,假设有一个答案X, 那图中必然存在至少一条路径上,比X长的边
数量小于等于X,二分时候每次验证这个约束是否成立即可

验证方法: 将长度大于X的边权重改为1,权重小于等于X的边权重改为0,然后求最短路,
最短路的数值就是所有路径中经过长度大于X的边的最少数量,如果这个数量小于等于K,
则X是一个合法值,二分搜索搜出来所有合法X的最小值即可
'''

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

class SPFA:

    # start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
    # 包含节点为1, 2, 3, 4, ..... max_node_num
    def __init__(self, start_node, edges, is_directed, max_node_num):
        self.edges = edges[::]
        self.start_node = start_node
        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)
        dis[self.start_node] = 0

        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()
        updated_nodes.append(self.start_node)
        in_que = [0] * (self.max_node_num + 1)
        in_que[self.start_node] = 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)]
        return dis



N, M, K = map(int, input().split())
all_w = set()
edges = []
for i in range(M):
    a, b, w = map(int, input().split())
    edges.append((a, b, w))
    all_w.add(w)

w_arr = list(all_w)
w_arr.sort()
w_arr = [0] + w_arr


def is_valid(X):
    e = [(a, b, 0) if w <= X else (a, b, 1) for a, b, w in edges]
    algo = SPFA(1, e, is_directed=False, max_node_num=N)
    dis = algo.getMinPathLen()
    return dis[N] <= K

l, r = 0, len(w_arr)-1
ans = -1
while l <= r:
    mid = l + (r-l) // 2
    if is_valid(w_arr[mid]):
        r = mid - 1
        ans = w_arr[mid]
    else:
        l = mid + 1

print(ans)





'''
题目的意思是在无向图中求1到N的所有可能路径中第K+1大的边的最小值是多少

可以进行二分,假设有一个答案X, 那图中必然存在至少一条路径上,比X长的边
数量小于等于X,二分时候每次验证这个约束是否成立即可

验证方法: 将长度大于X的边权重改为1,权重小于等于X的边权重改为0,然后求最短路,
最短路的数值就是所有路径中经过长度大于X的边的最少数量,如果这个数量小于等于K,
则X是一个合法值,二分搜索搜出来所有合法X的最小值即可
'''

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

class SPFA:

    # start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
    # 包含节点为1, 2, 3, 4, ..... max_node_num
    def __init__(self, start_node, edges, is_directed, max_node_num):
        self.edges = edges[::]
        self.start_node = start_node
        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)
        dis[self.start_node] = 0

        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()
        updated_nodes.append(self.start_node)
        in_que = [0] * (self.max_node_num + 1)
        in_que[self.start_node] = 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)]
        return dis



N, M, K = map(int, input().split())
all_w = set()
edges = []
for i in range(M):
    a, b, w = map(int, input().split())
    edges.append((a, b, w))
    all_w.add(w)

w_arr = list(all_w)
w_arr.sort()
w_arr = [0] + w_arr


def is_valid(X):
    e = [(a, b, 0) if w <= X else (a, b, 1) for a, b, w in edges]
    algo = SPFA(1, e, is_directed=False, max_node_num=N)
    dis = algo.getMinPathLen()
    return dis[N] <= K

l, r = 0, len(w_arr)-1
ans = -1
while l <= r:
    mid = l + (r-l) // 2
    if is_valid(w_arr[mid]):
        r = mid - 1
        ans = w_arr[mid]
    else:
        l = mid + 1

print(ans)




活动打卡代码 AcWing 1135. 新年好

from typing import List, Tuple
from queue import PriorityQueue
from itertools import permutations


'''
先求6个点相互之间的距离,然后dfs枚举路线的所有可能排列
'''

n, m = map(int, input().split())
arr = list(map(int, input().split()))


from collections import deque

class SPFA:

    # start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
    # 包含节点为1, 2, 3, 4, ..... max_node_num
    def __init__(self, start_node, edges, is_directed, max_node_num):
        self.edges = edges[::]
        self.start_node = start_node
        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)
        dis[self.start_node] = 0

        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()
        updated_nodes.append(self.start_node)
        in_que = [0] * (self.max_node_num + 1)
        in_que[self.start_node] = 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) if node == 1 or node in arr }
        return dis


edges = []
for i in range(m):
    a, b, w = map(int, input().split())
    edges.append((a,b,w))
    edges.append((b,a,w))

dist = {}

for start_node in [1, arr[0], arr[1], arr[2], arr[3], arr[4]]:
    dist[(start_node, start_node)] = 0
    algo = SPFA(start_node, edges, is_directed=False, max_node_num=n)
    ans = algo.getMinPathLen()
    for next in [1, arr[0], arr[1], arr[2], arr[3], arr[4]]:
        if next != start_node:
            dist[(start_node, next)] = ans[next]

min_total = 0x7fffffff
visit = {1}

def dfs(cur, sum):
    if len(visit) == 6:
        return sum

    ans = 0x7fffffff
    for next in arr:
        if next not in visit:
            visit.add(next)
            ans = min(ans, dfs(next, sum + dist[(cur, next)]))
            visit.remove(next)

    return ans

print(dfs(1, 0))




from typing import List, Tuple
from queue import PriorityQueue
from itertools import permutations


'''
先求6个点相互之间的距离,然后dfs枚举路线的所有可能排列
'''

n, m = map(int, input().split())
arr = list(map(int, input().split()))


from collections import deque

class SPFA:

    # start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
    # 包含节点为1, 2, 3, 4, ..... max_node_num
    def __init__(self, start_node, edges, is_directed, max_node_num):
        self.edges = edges[::]
        self.start_node = start_node
        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)
        dis[self.start_node] = 0

        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()
        updated_nodes.append(self.start_node)
        in_que = [0] * (self.max_node_num + 1)
        in_que[self.start_node] = 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) if node == 1 or node in arr }
        return dis


edges = []
for i in range(m):
    a, b, w = map(int, input().split())
    edges.append((a,b,w))
    edges.append((b,a,w))

dist = {}

for start_node in [1, arr[0], arr[1], arr[2], arr[3], arr[4]]:
    dist[(start_node, start_node)] = 0
    algo = SPFA(start_node, edges, is_directed=False, max_node_num=n)
    ans = algo.getMinPathLen()
    for next in [1, arr[0], arr[1], arr[2], arr[3], arr[4]]:
        if next != start_node:
            dist[(start_node, next)] = ans[next]

min_total = 0x7fffffff
visit = {1}

def dfs(cur, sum):
    if len(visit) == 6:
        return sum

    ans = 0x7fffffff
    for next in arr:
        if next not in visit:
            visit.add(next)
            ans = min(ans, dfs(next, sum + dist[(cur, next)]))
            visit.remove(next)

    return ans

print(dfs(1, 0))






'''
建图方式
构造一个虚拟节点0, 0 到每一个物品的边权是物品本来价格,然后每个物品的可替代物品到
被替代物品间边权值是替代价格,问题转换成求0号点到1号点的最短距离,合法的方案中一定是
所有方案的等级差值在M以内,所以枚举所有长度是M+1的连续等级区间,每个区间选出在区间
中的物品,用这些物品构造有向图求最短距离,找出每个区间对应的最短距离的最小值即可
'''

from collections import deque

class SPFA:

    # start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
    def __init__(self, start_node, edges, is_directed, max_node_num):
        self.edges = edges[::]
        self.start_node = start_node
        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)
        dis[self.start_node] = 0

        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()
        updated_nodes.append(self.start_node)
        in_que = [0] * (self.max_node_num + 1)
        in_que[self.start_node] = 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)]



M, N = map(int, input().split())
product = [[0, 0, []] for _ in range(N+1)]

for i in range(1, N+1):
    product[i][0], product[i][1], x = map(int, input().split())
    product[i][2] = []
    for _ in range(x):
        t, v = map(int, input().split())
        product[i][2].append((t, v))

min_cost = 0x7fffffff
for lower in range(product[1][1] - M, product[1][1] + 1):
    upper = lower + M
    edges = []
    for i in range(1, N+1):
        if product[i][1] >= lower and product[i][1] <= upper:
            edges.append( (0, i, product[i][0]) )
            for id, price in product[i][2]:
                if product[id][1] >= lower and product[id][1] <= upper:
                    edges.append( (id, i, price) )
                    edges.append( (0, id, product[id][0]) )


    algo = SPFA(0, edges, is_directed=True, max_node_num = N)
    ans = algo.getMinPathLen()
    for k, v in ans:
        if k == 1:
            min_cost = min(min_cost, v)
            break

print(min_cost)




活动打卡代码 AcWing 903. 昂贵的聘礼

'''
建图方式
构造一个虚拟节点0, 0 到每一个物品的边权是物品本来价格,然后每个物品的可替代物品到
被替代物品间边权值是替代价格,问题转换成求0号点到1号点的最短距离,合法的方案中一定是
所有方案的等级差值在M以内,所以枚举所有长度是M+1的连续等级区间,每个区间选出在区间
中的物品,用这些物品构造有向图求最短距离,找出每个区间对应的最短距离的最小值即可
'''

from collections import deque

class SPFA:

    # start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
    def __init__(self, start_node, edges, is_directed, max_node_num):
        self.edges = edges[::]
        self.start_node = start_node
        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)
        dis[self.start_node] = 0

        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()
        updated_nodes.append(self.start_node)
        in_que = [0] * (self.max_node_num + 1)
        in_que[self.start_node] = 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)]



M, N = map(int, input().split())
product = [[0, 0, []] for _ in range(N+1)]

for i in range(1, N+1):
    product[i][0], product[i][1], x = map(int, input().split())
    product[i][2] = []
    for _ in range(x):
        t, v = map(int, input().split())
        product[i][2].append((t, v))

min_cost = 0x7fffffff
for lower in range(product[1][1] - M, product[1][1] + 1):
    upper = lower + M
    edges = []
    for i in range(1, N+1):
        if product[i][1] >= lower and product[i][1] <= upper:
            edges.append( (0, i, product[i][0]) )
            for id, price in product[i][2]:
                if product[id][1] >= lower and product[id][1] <= upper:
                    edges.append( (id, i, price) )
                    edges.append( (0, id, product[id][0]) )


    algo = SPFA(0, edges, is_directed=True, max_node_num = N)
    ans = algo.getMinPathLen()
    for k, v in ans:
        if k == 1:
            min_cost = min(min_cost, v)
            break

print(min_cost)