[白俊17835]面接の勝範です

8192 ワード
パイ 金貨。 アルゴリズム#アルゴリズム# 白駿 コーディングテスト テキストリンク

1.問題の説明


面接の勝範ですね。

2.問題分析


都市から面接場までの最短距離をドエストラアルゴリズムで求めた後,最低価格と都市番号を求めた.
  • 都市から面接場までの距離ではなく、面接場から都市までの距離です.一方向図なので、図を実現する際に逆に実現します.ダエストラアルゴリズムは,同様に開始点(面接場)をすべて優先順位キューに配置して回転する.最終的に欲しい結果は면접장에서 가장 가까운 도시까지 걸리는 거리 중 최댓값だったからです.

    • 3.私の回答

    import sys
import heapq
from collections import deque

INF = sys.maxsize
n, m, k = map(int, sys.stdin.readline().rstrip().split())
nodes = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    nodes[b].append([a, c])
interviews = list(map(int, sys.stdin.readline().rstrip().split()))

def Dijkstra():
    distances = [INF for _ in range(n+1)]
    pq = []
    for interview in interviews:
        heapq.heappush(pq, [0, interview])
        distances[interview] = 0

    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

distances = Dijkstra()
dist = max(distances[1:])
print(distances.index(dist))
print(dist)
    [Android/Kotlin] Transformations.map() vs switchMap()
    PANDAS : loc, iloc