結果

問題 No.1320 Two Type Min Cost Cycle
ユーザー Navier_Boltzmann
提出日時 2024-07-06 16:03:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,429 ms / 2,000 ms
コード長 1,675 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 82,472 KB
実行使用メモリ 108,280 KB
最終ジャッジ日時 2024-07-06 16:04:10
合計ジャッジ時間 17,343 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff # 

# import pypyjit
# pypyjit.set_param("max_unroll_recursion=-1")
from collections import *
from functools import *
from itertools import *
from heapq import *
import sys, math
# sys.setrecursionlimit(10**4)
input = sys.stdin.readline
INF = (1<<60)
def dijkstra(s,e):
    
    N = len(e)
    dist = [INF]*N
    dist[s]=0
    h = []
    bef = [-1]*N
    heappush(h,s)
    while h:
        nw,v = divmod(heappop(h),N)
        if dist[v]!=nw:
            continue
        for iv,ic in e[v]:
            nc = ic + nw
            if nc < dist[iv]:
                bef[iv] = v
                dist[iv] = nc
                heappush(h,nc*N + iv)
    return dist,bef
def answer1():
    N,M = map(int,input().split())
    e = [[] for _ in range(N)]
    for _ in range(M):
        u,v,w = map(int,input().split())
        u -= 1
        v -= 1
        e[u].append((v,w))
    ans = INF
    d = [dijkstra(s,e)[0] for s in range(N)]
    for i in range(N-1):
        for j in range(i+1,N):
            ans = min(ans,d[i][j] + d[j][i])
    if ans==INF:
        print(-1)
    else:
        print(ans)
    return

def answer0():
    N,M = map(int,input().split())
    e = [[] for _ in range(N)]
    for _ in range(M):
        u,v,w = map(int,input().split())
        u -= 1
        v -= 1
        e[u].append((v,w))
        e[v].append((u,w))

    ans = INF
    for r in range(N):
        dist,bef = dijkstra(r,e)

        for i in range(N):
            for j,wj in e[i]:

                if (bef[i]!=j)&(bef[j]!=i):
                    ans = min(ans,dist[i]+dist[j]+wj)
    if ans==INF:
        print(-1)
    else:
        print(ans)
T = int(input())
if T==1:
    answer1()
else:
    answer0()
0