結果

問題 No.2805 Go to School
ユーザー D M
提出日時 2025-02-12 13:01:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,201 ms / 2,000 ms
コード長 1,892 bytes
コンパイル時間 447 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 152,736 KB
最終ジャッジ日時 2025-02-12 13:02:16
合計ジャッジ時間 23,297 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import heapq
from collections import defaultdict
n,m,l,s,e=map(int,input().split())
def dijkstra(graph, start):
    """
    ダイクストラ法を用いて、startから各頂点への最短距離を求めます。
    Parameters:
        graph: dict
            各頂点をキーとし、その頂点から出る辺を (隣接頂点, 重み) のタプルのリストとして持つ辞書
            例:
                graph = {
                    0: [(1, 2), (2, 5)],
                    1: [(2, 1), (3, 3)],
                    2: [(3, 1)],
                    3: []
                }
        start: 始点となる頂点
    Returns:
        dist: dict
            各頂点への最短距離を表す辞書。到達不能の場合は float('inf') が設定されます。
    """
    # 各頂点への最短距離を無限大で初期化（始点のみ0）
    dist = {vertex: float('inf') for vertex in graph}
    dist[start] = 0
    # 優先度付きキュー（ヒープ）に (距離, 頂点) のペアを格納
    queue = [(0, start)]
    while queue:
        current_dist, u = heapq.heappop(queue)
        # すでにより良い経路が見つかっている場合はスキップ
        if current_dist > dist[u]:
            continue
        # uから出る全ての辺について、最短距離を更新
        for v, weight in graph[u]:
            new_dist = current_dist + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(queue, (new_dist, v))
    return dist
G=defaultdict(list)
for _ in range(m):
    a,b,t=map(int,input().split())
    G[a].append((b,t))
    G[b].append((a,t))
D1=dijkstra(G,1)
D2=dijkstra(G,n)
T=list(map(int,input().split()))
ans=float("inf")
for i in T:
    if i in D1 and i in D2 and D1[i]<=s+e:
        ans=min(ans,max(s,D1[i])+1+D2[i])
print(ans if ans!=float("inf") else -1)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0