結果
問題 | No.2695 Warp Zone |
ユーザー |
![]() |
提出日時 | 2024-03-22 22:12:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 804 ms / 2,000 ms |
コード長 | 1,938 bytes |
コンパイル時間 | 233 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 303,488 KB |
最終ジャッジ日時 | 2024-09-30 11:41:27 |
合計ジャッジ時間 | 9,334 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
import ioimport sysfrom collections import defaultdict, deque, Counterfrom itertools import permutations, combinations, accumulatefrom heapq import heappush, heappopfrom bisect import bisect_right, bisect_leftfrom math import gcdimport math_INPUT = """\63 3 11 2 3 25 4 22 4 1 24 4 2 110 10 54 5 3 34 6 6 108 8 10 59 5 3 19 3 3 4"""def Dijkstra(G,s):done=[False]*len(G)inf=10**20C=[inf]*len(G)C[s]=0h=[]heappush(h,(0,s))while h:x,y=heappop(h)if done[y]:continuedone[y]=Truefor v in G[y]:if C[v[1]]>C[y]+v[0]:C[v[1]]=C[y]+v[0]heappush(h,(C[v[1]],v[1]))return Cdef input():return sys.stdin.readline()[:-1]def solve(test):H,W,N=map(int, input().split())warp=[list(map(int, input().split())) for _ in range(N)]G=[[] for _ in range(2*N+2)]z=[]for i in range(N):a,b,c,d=warp[i]G[2*i].append((1,2*i+1))z.append((a,b))z.append((c,d))z.append((1,1))z.append((H,W))for i in range(2*N+2):a,b=z[i]for j in range(i+1,2*N+2):c,d=z[j]G[i].append((abs(a-c)+abs(b-d),j))G[j].append((abs(a-c)+abs(b-d),i))print(Dijkstra(G,2*N)[2*N+1])def random_input():from random import randint,shuffleN=randint(1,10)M=randint(1,N)A=list(range(1,M+1))+[randint(1,M) for _ in range(N-M)]shuffle(A)return (" ".join(map(str, [N,M]))+"\n"+" ".join(map(str, A))+"\n")*3def simple_solve():return []def main(test):if test==0:solve(0)elif test==1:sys.stdin = io.StringIO(_INPUT)case_no=int(input())for _ in range(case_no):solve(0)else:for i in range(1000):sys.stdin = io.StringIO(random_input())x=solve(1)y=simple_solve()if x!=y:print(i,x,y)print(*[line for line in sys.stdin],sep='')break#0:提出用、1:与えられたテスト用、2:ストレステスト用main(0)