結果

問題 No.3564 Awkward Timing
コンテスト
ユーザー えりす
提出日時 2026-06-04 08:33:45
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 883 ms / 2,000 ms
コード長 1,226 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 509 ms
コンパイル使用メモリ 85,504 KB
実行使用メモリ 188,968 KB
最終ジャッジ日時 2026-06-04 08:34:26
合計ジャッジ時間 39,465 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 40 % AC * 38
満点 60 % AC * 62
合計 100 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys, heapq
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def solve():
    it = iter(sys.stdin.buffer.read().split())
    n = int(next(it))
    m = int(next(it))
    k = int(next(it))
    g = []
    for _ in range(n + 1):
        g.append([])
    e = []
    for _ in range(m):
        u = int(next(it))
        v = int(next(it))
        t = int(next(it))
        g[u].append((v, t))
        g[v].append((u, t))
        e.append((u, v, t))
    INF = 10 ** 30
    d = [INF] * (n + 1)
    d[1] = 0
    que = [(0, 1)]
    while que:
        cur, v = heapq.heappop(que)
        if cur > d[v]:
            continue
        for j in range(len(g[v])):
            u = g[v][j][0]
            t = g[v][j][1]
            nxt = cur + t
            if nxt < d[u]:
                d[u] = nxt
                heapq.heappush(que, (nxt, u))
    gd = 0
    for i in range(len(e)):
        u = e[i][0]
        v = e[i][1]
        t = e[i][2]
        if d[u] != INF:
            gd = gcd(gd, abs(d[u] + t - d[v]))
        if d[v] != INF:
            gd = gcd(gd, abs(d[v] + t - d[u]))
    if gd == 0:
        ans = d[n] % k
    else:
        ans = d[n] % gcd(gd, k)
    print(ans)

if __name__ == '__main__':
    solve()
0