結果

問題 No.3564 Awkward Timing
コンテスト
ユーザー detteiuu
提出日時 2026-05-31 05:43:09
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 1,761 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 452 ms
コンパイル使用メモリ 85,376 KB
実行使用メモリ 233,908 KB
最終ジャッジ日時 2026-05-31 05:43:49
合計ジャッジ時間 38,260 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 40 % AC * 38
満点 60 % AC * 60 WA * 2
合計 40 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from sys import stdin
input = stdin.readline
from heapq import heappush, heappop
from math import gcd
from types import GeneratorType

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
            else:
                stack.pop()
                if not stack:
                    break
                to = stack[-1].send(to)
        return to
    return wrappedfunc

@bootstrap
def dfs(n, p):
    for v, c in G[n]:
        base.append(c*2)
        if v == p: continue
        if dist[v] == -1:
            dist[v] = dist[n]+c
            yield dfs(v, n)
        elif dist[v] < dist[n]:
            res = dist[n]-dist[v]+c
            base.append(res)
    yield

N, M, K = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    u, v, c = map(int, input().split())
    u, v = u-1, v-1
    G[u].append((v, c))
    G[v].append((u, c))

dist = [-1]*N
dist[0] = 0
base = []
dfs(0, -1)

for i in range(N):
    for v, c in G[i]:
        if i == v:
            base.append(c)

def dijkstra(start):
    INF = 10**18
    dist = [INF]*N
    dist[start] = 0
    visited = [False]*N
    que = [(0, start)]
    while que:
        d, now = heappop(que)
        if visited[now]:
            continue
        visited[now] = True
        for next, weight in G[now]:
            if dist[now]+weight < dist[next]:
                dist[next] = dist[now]+weight
                heappush(que, (dist[next], next))
    return dist

dist = dijkstra(0)
GCD = 0
for b in base:
    GCD = gcd(GCD, b)

GCD = gcd(GCD, K)

print(dist[-1]%GCD)
0