結果
問題 | No.788 トラックの移動 |
ユーザー | vwxyz |
提出日時 | 2022-03-24 04:49:51 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,435 bytes |
コンパイル時間 | 291 ms |
コンパイル使用メモリ | 87,164 KB |
実行使用メモリ | 114,004 KB |
最終ジャッジ日時 | 2023-08-21 17:40:58 |
合計ジャッジ時間 | 13,860 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | AC | 80 ms
71,396 KB |
testcase_02 | AC | 81 ms
71,460 KB |
testcase_03 | AC | 81 ms
71,500 KB |
testcase_04 | AC | 601 ms
87,064 KB |
testcase_05 | TLE | - |
testcase_06 | TLE | - |
testcase_07 | AC | 80 ms
71,480 KB |
testcase_08 | AC | 79 ms
71,144 KB |
testcase_09 | AC | 81 ms
71,616 KB |
testcase_10 | AC | 82 ms
71,316 KB |
testcase_11 | AC | 79 ms
71,400 KB |
testcase_12 | AC | 79 ms
71,396 KB |
testcase_13 | AC | 78 ms
71,404 KB |
testcase_14 | AC | 80 ms
71,540 KB |
testcase_15 | AC | 588 ms
110,528 KB |
testcase_16 | TLE | - |
ソースコード
import sys readline=sys.stdin.readline import heapq class Graph: def __init__(self,V,edges=False,graph=False,directed=False,weighted=False,inf=float("inf")): self.V=V self.directed=directed self.weighted=weighted self.inf=inf self.graph=graph def Dijkstra(self,s,route_restoration=False): dist=[self.inf]*self.V dist[s]=0 hq=[(0,s)] if route_restoration: parents=[None]*self.V while hq: dx,x=heapq.heappop(hq) if dist[x]<dx: continue for y,dy in self.graph[x]: if dist[y]>dx+dy: dist[y]=dx+dy if route_restoration: parents[y]=x heapq.heappush(hq,(dist[y],y)) if route_restoration: return dist,parents else: return dist N,M,L=map(int,readline().split()) L-=1 T=list(map(int,readline().split())) graph=[[] for i in range(N)] for _ in range(M): a,b,c=map(int,readline().split()) a-=1;b-=1 graph[a].append((b,c)) graph[b].append((a,c)) inf=1<<60 G=Graph(N,graph=graph,weighted=True,inf=inf) dist=[G.Dijkstra(i) for i in range(N)] ans=inf idx=[j for j in range(N) if T[j]] for i in range(N): s=sum(T[j]*dist[i][j] for j in range(N))*2 if s: s+=min(dist[L][j]-dist[i][j] for j in idx) ans=min(ans,s) print(ans)