[白俊20010]悪徳領主恵儒
1.問題の説明
悪徳領主慧柔
2.問題分析
クルーズでMSTとMST用の幹線を記録できます.MSTで使用する幹線でグラフを生成し,あるノードから別のノードへの経路長の中で最も長い値を複数のアルゴリズムで求めることができる.
3.私の回答 import sys
import heapq
INF = sys.maxsize
n, k = map(int, sys.stdin.readline().rstrip().split())
pq = []
for _ in range(k):
a, b, c = map(int, sys.stdin.readline().rstrip().split())
heapq.heappush(pq, [c, a, b])
def find(node):
if parents[node] == node: return node
else:
parents[node] = find(parents[node])
return parents[node]
def union(node1, node2):
root1 ,root2 = find(node1), find(node2)
if root1 == root2: return False
else:
parents[root2] = root1
return True
def Dijkstra(nodes, start):
distances = [INF for _ in range(n)]
distances[start] = 0
pq = []
heapq.heappush(pq, [0, start])
while pq:
cur_cost, cur_node = heapq.heappop(pq)
if distances[cur_node] < cur_cost: continue
for next_node, next_cost in nodes[cur_node]:
if distances[next_node] > cur_cost + next_cost:
distances[next_node] = cur_cost + next_cost
heapq.heappush(pq, [cur_cost + next_cost, next_node])
return distances
def Kruskal():
total = 0
nodes = [[] for _ in range(n)]
while pq:
cost, node1, node2 = heapq.heappop(pq)
if union(node1, node2):
nodes[node1].append([node2, cost])
nodes[node2].append([node1, cost])
total += cost
print(total)
# 크루스칼 알고리즘을 통해 MST 구한다. MST에 사용한 간선을 nodes에 기록한다.
local_max = 0
for i in range(n):
distances = Dijkstra(nodes, i)
local_max = max(local_max, max(distances))
# nodes를 통해 각 노드에서 다른 모든 노드에 대한 최단 거리를 다익스트라 알고리즘을 통해 구한다.
# 최댓값을 local_max에 갱신한다.
print(local_max)
parents = [i for i in range(n)]
Kruskal()
Reference
この問題について([白俊20010]悪徳領主恵儒), 我々は、より多くの情報をここで見つけました
https://velog.io/@j_aion/백준-20010-악덕-영주-혜유
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
クルーズでMSTとMST用の幹線を記録できます.MSTで使用する幹線でグラフを生成し,あるノードから別のノードへの経路長の中で最も長い値を複数のアルゴリズムで求めることができる.
3.私の回答 import sys
import heapq
INF = sys.maxsize
n, k = map(int, sys.stdin.readline().rstrip().split())
pq = []
for _ in range(k):
a, b, c = map(int, sys.stdin.readline().rstrip().split())
heapq.heappush(pq, [c, a, b])
def find(node):
if parents[node] == node: return node
else:
parents[node] = find(parents[node])
return parents[node]
def union(node1, node2):
root1 ,root2 = find(node1), find(node2)
if root1 == root2: return False
else:
parents[root2] = root1
return True
def Dijkstra(nodes, start):
distances = [INF for _ in range(n)]
distances[start] = 0
pq = []
heapq.heappush(pq, [0, start])
while pq:
cur_cost, cur_node = heapq.heappop(pq)
if distances[cur_node] < cur_cost: continue
for next_node, next_cost in nodes[cur_node]:
if distances[next_node] > cur_cost + next_cost:
distances[next_node] = cur_cost + next_cost
heapq.heappush(pq, [cur_cost + next_cost, next_node])
return distances
def Kruskal():
total = 0
nodes = [[] for _ in range(n)]
while pq:
cost, node1, node2 = heapq.heappop(pq)
if union(node1, node2):
nodes[node1].append([node2, cost])
nodes[node2].append([node1, cost])
total += cost
print(total)
# 크루스칼 알고리즘을 통해 MST 구한다. MST에 사용한 간선을 nodes에 기록한다.
local_max = 0
for i in range(n):
distances = Dijkstra(nodes, i)
local_max = max(local_max, max(distances))
# nodes를 통해 각 노드에서 다른 모든 노드에 대한 최단 거리를 다익스트라 알고리즘을 통해 구한다.
# 최댓값을 local_max에 갱신한다.
print(local_max)
parents = [i for i in range(n)]
Kruskal()
Reference
この問題について([白俊20010]悪徳領主恵儒), 我々は、より多くの情報をここで見つけました
https://velog.io/@j_aion/백준-20010-악덕-영주-혜유
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
import sys
import heapq
INF = sys.maxsize
n, k = map(int, sys.stdin.readline().rstrip().split())
pq = []
for _ in range(k):
a, b, c = map(int, sys.stdin.readline().rstrip().split())
heapq.heappush(pq, [c, a, b])
def find(node):
if parents[node] == node: return node
else:
parents[node] = find(parents[node])
return parents[node]
def union(node1, node2):
root1 ,root2 = find(node1), find(node2)
if root1 == root2: return False
else:
parents[root2] = root1
return True
def Dijkstra(nodes, start):
distances = [INF for _ in range(n)]
distances[start] = 0
pq = []
heapq.heappush(pq, [0, start])
while pq:
cur_cost, cur_node = heapq.heappop(pq)
if distances[cur_node] < cur_cost: continue
for next_node, next_cost in nodes[cur_node]:
if distances[next_node] > cur_cost + next_cost:
distances[next_node] = cur_cost + next_cost
heapq.heappush(pq, [cur_cost + next_cost, next_node])
return distances
def Kruskal():
total = 0
nodes = [[] for _ in range(n)]
while pq:
cost, node1, node2 = heapq.heappop(pq)
if union(node1, node2):
nodes[node1].append([node2, cost])
nodes[node2].append([node1, cost])
total += cost
print(total)
# 크루스칼 알고리즘을 통해 MST 구한다. MST에 사용한 간선을 nodes에 기록한다.
local_max = 0
for i in range(n):
distances = Dijkstra(nodes, i)
local_max = max(local_max, max(distances))
# nodes를 통해 각 노드에서 다른 모든 노드에 대한 최단 거리를 다익스트라 알고리즘을 통해 구한다.
# 최댓값을 local_max에 갱신한다.
print(local_max)
parents = [i for i in range(n)]
Kruskal()
Reference
この問題について([白俊20010]悪徳領主恵儒), 我々は、より多くの情報をここで見つけました https://velog.io/@j_aion/백준-20010-악덕-영주-혜유テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol