結果

問題 No.3653 Space-Time Courier
コンテスト
ユーザー sig
提出日時 2026-08-28 22:27:58
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 1,677 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 239 ms
コンパイル使用メモリ 96,108 KB
実行使用メモリ 267,908 KB
最終ジャッジ日時 2026-08-28 22:28:54
合計ジャッジ時間 33,819 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 23 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#t = int(input())
tt = 1
import random
R = random.randint(1, 1 << 60)
from collections import deque
from heapq import heappush, heappop

INF = 10**30
def Johnson(G, N):
    h = [0]*N

    update = 1
    for i in range(N):
        update = 0
        for v in range(N):
            d = h[v]
            for w, c in G[v]:
                if c + d < h[w]:
                    h[w] = d + c
                    update = 1
        if not update:
            break
    else:
        return None

    for v in range(N):
        d = h[v]
        g = G[v]
        for j, (w, c) in enumerate(g):
            g[j] = (w, c + d - h[w])

    D = []
    for i in range(N):
        dst = [INF]*N
        dst[i] = 0
        que = [(0, i)]
        while que:
            cost, v = heappop(que)
            if dst[v] < cost:
                continue
            for w, c in G[v]:
                if cost + c < dst[w]:
                    dst[w] = r = cost + c
                    heappush(que, (r, w))
        v = h[i]
        for j in range(N):
            if dst[j] == INF:
                dst[j] = INF
            else:
                dst[j] -= v - h[j]
        D.append(dst)

    return D
for _ in range(tt):
  n,m = map(int, input().split())
  p = list(map(int, input().split()))
  edge = [[] for _ in range(n)]
  for i in range(m):
    u,v,t = map(int, input().split())
    u -= 1
    v -= 1
    edge[u].append([v,t])
  dis = Johnson(edge,n)
  mi = 10**30
  ko = 0
  for i in range(n):
    for j in range(i+1,n):
      cur = dis[i][j]+p[i]+p[j]
      if cur == mi:
        ko += 1
      elif cur < mi:
        mi = cur
        ko = 1
  if mi == 10**30:
    print(-1)
  else:
    print(mi,ko)
0