fork download
copy 
  1. import heapq
  2.  
  3. def wf( mp):
  4.   h, w = len(mp), len(mp[0])
  5.   for i in range(h*w):
  6.     if mp[i//w][i%w]=='S': str =i
  7.     if mp[i//w][i%w]=='G': gol =i
  8.   a = [[999999] * (h*w) for _ in range(h*w)]
  9.   for i in range(h*w): a[i][i] = 0
  10.   for i in range(h):
  11.     for j in range(w):
  12.       ch = mp[i][j]
  13.       dst = 0 if ch=='S' or ch=='G' else int(ch)
  14.       if i>0: a[(i-1)*w+j][i*w+j] = dst
  15.       if j>0: a[i*w+(j-1)][i*w+j] = dst
  16.       if i<h-1:a[(i+1)*w+j][i*w+j] =dst
  17.       if j<w-1: a[i*w+j+1][i*w+j] = dst
  18.   for k in range(h*w):
  19.     for i in range(h*w):
  20.       for j in range(h*w):
  21.           a[i][j] = min(a[i][j], a[i][k] + a[k][j])
  22.   #print(a)
  23.   print("\t\t(wf-ans=%d)" %a[str][gol])
  24.  
  25. ### spfa 単一始点最短路
  26. import collections # g = [[] for _ in range(n)]
  27. inf = 10**14
  28. def spfa(mp):
  29.   h, w = len(mp), len(mp[0])
  30.   for i in range(h*w):
  31.     if mp[i//w][i%w]=='S': sy, sx = i//w, i%w
  32.     if mp[i//w][i%w]=='G': gy, gx = i//w, i%w
  33.   dr = [0, 1, 0, -1, 0]
  34.   qu = []
  35.   inQ = [[False] * w for _ in range(h)]
  36.   ds = [[999999] * w for _ in range(h)]
  37.   ds[sy][sx] = 0
  38.  
  39.  
  40.   qu = collections.deque()
  41.   qu.append(sy*w+sx)
  42.   while qu:
  43.     cr = qu.popleft()
  44.     cy, cx = cr//w, cr%w
  45.     inQ[cy][cx] = False
  46.  
  47.     for j in range(4):
  48.       ny, nx = cy + dr[j], cx + dr[j+1]
  49.       if ny<0 or ny>=h or nx<0 or nx>=w: continue
  50.       nd = mp[ny][nx]
  51.       if nd =='G' or nd=='S': nd = '0'
  52.       if ds[ny][nx] <= ds[cy][cx] + int(nd): continue
  53.       ds[ny][nx] = ds[cy][cx] + int(nd)
  54.       if inQ[ny][nx]: continue
  55.       qu.append(ny*w+nx)
  56.       inQ[ny][nx] = True
  57.   return ds[gy][gx]
  58.   ### 
  59.  
  60.  
  61. def dujkstra( mp):
  62.   h, w = len(mp), len(mp[0])
  63.   for i in range(h*w):
  64.     if mp[i//w][i%w]=='S': sy, sx = i//w, i%w
  65.     if mp[i//w][i%w]=='G': gy, gx = i//w, i%w
  66.   dr = [0, 1, 0, -1]
  67.   qa = []
  68.   pre = [[-1] * w for _ in range(h)]
  69.   ds = [[11*h*w] * w for _ in range(h)]
  70.   ds[sy][sx] = 0
  71.   heapq.heappush(qa, [0, sy, sx])
  72.   while len(qa) >0:
  73.     cd, cy,cx = heapq.heappop(qa)
  74.     if ds[cy][cx] < cd: continue
  75.     for i in range(4):
  76.       ny = cy+dr[i]; nx = cx+dr[i^1]
  77.       if ny<0 or ny>=h or nx<0 or nx>=w: continue
  78.       nd = mp[ny][nx]
  79.       if nd =='G' or nd=='S': nd = '0'
  80.       if ds[cy][cx] + int(nd) < ds[ny][nx]:
  81.         ds[ny][nx] = ds[cy][cx] + int(nd)
  82.         heapq.heappush(qa, [ds[ny][nx], ny, nx])
  83.         pre[ny][nx] = cy*w+cx
  84.  
  85. # 以下 経路表示
  86.   dmp=[['.'] * w for _ in range(h)]
  87.   dmp[sy][sx] ='S'; dmp[gy][gx] ='G'
  88.   cy, cx = gy, gx
  89.   while True:
  90.     su = pre[cy][cx]
  91.     cy, cx = su//w, su%w
  92.     if mp[cy][cx] == 'S': break
  93.     dmp[cy][cx] = mp[cy][cx]
  94.   for i,a in  enumerate(dmp):
  95.     if w<45 : print("%s   %s"%(''.join(a), mp[i]))
  96.     else : print("%s " %(''.join(a)))
  97.   return  ds[gy][gx]
  98.  
  99.  
  100.  
  101. hdoc = """
  102. S5111
  103. 1115G
  104.  
  105. S1111
  106. 98642
  107. G1111
  108.  
  109. 13457689768914512071934123457
  110. G4578901258901212890361125312
  111. 37890423076834712378998725463
  112. 16890102569615902061456259893
  113. 34582934765923812893461515232
  114. 57896123896741378915691551697
  115. 89013897456123457162501835479
  116. 21389046013845610034623405686
  117. 8902346203948612341356362342S
  118.  
  119. """
  120.  
  121.  
  122. nmp=[]
  123. for ln in hdoc.split('\n'):
  124.   if len(ln) < 4 and len(nmp) > 0:
  125.     #for s in nmp: print(s)
  126.     print("   ===> %d" %dujkstra(nmp))
  127.     wf(nmp)
  128.     print("\t\t(spfa-ans=%d)\n" %spfa(nmp))
  129.     nmp = []
  130.   if len(ln) >3: nmp.append(ln)
  131.  
  132.  
Success #stdin #stdout 0.23s 67824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
S.111   S5111
111.G   1115G
   ===> 6
		(wf-ans=6)
		(spfa-ans=6)

S....   S1111
9....   98642
G....   G1111
   ===> 9
		(wf-ans=9)
		(spfa-ans=9)

.............................   13457689768914512071934123457
G4578.0125890121.............   G4578901258901212890361125312
....0.2........1.............   37890423076834712378998725463
....010........02061.........   16890102569615902061456259893
...................3461......   34582934765923812893461515232
......................1......   57896123896741378915691551697
......................1......   89013897456123457162501835479
......................340....   21389046013845610034623405686
........................2342S   8902346203948612341356362342S
   ===> 100
		(wf-ans=100)
		(spfa-ans=100)
https://ideone.com/DV1w4s
お題スレ Part13 316 ダイクストラ
language:
Python (PyPy 2.7.13)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!