'''
将每一个无向边连起来的连通块看成一个大的点,大点之间用可能是负权的边连接起来,把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])