题目记录

蓝桥杯
https://www.lanqiao.cn/problems/17118/learning/

最短路-迪杰斯特拉-堆优化版
此贴仅为个人做题记录，无参考性

如下代码为看错题目版，以为纯看高度，行列皆可依靠高度到达

对于如下案例有意思

10
6 75 42 57 18 75 86 40 29 97
82 7 77 68 66 24 98 8 85 98
64 28 90 7 40 62 60 13 1 57
42 36 24 94 89 27 2 31 57 64
94 6 48 63 31 6 39 7 88 11
55 98 75 22 39 0 39 54 86 25
53 90 33 13 0 93 24 77 0 70
99 40 22 4 62 26 73 37 40 33
92 61 54 82 17 28 92 57 4 48
74 86 39 87 69 58 30 74 2 96

from heapq import *
n = int(input())
s = []
for i in range(n):
  ss=list(map(int,input().split()))
  s.append(ss)
I_max = float("inf")
N = 1000010
e = [0]*N
ne = [0]*N
ne[0]=-1
h = [0]*N
weight = [I_max]*N
idx = 0
dist = [I_max]*N#距离
IS = [0]*N
def add(x,y,z):
    global idx
    idx+=1
    e[idx] = y
    weight[idx] = z
    ne[idx] = h[x]
    h[x] = idx
def dijkstra():
    dist[1]=0
    d = []
    heappush(d,[0,1])
    while d:
        t = heappop(d)
        ver = t[1]
        if IS[ver]:
            continue
        IS[ver] = 1
        distance = t[0]
        print(t)
        i = h[ver]
        while i!=-1:
            j = e[i]
            if distance+weight[i]<dist[j]:
                dist[j] = distance+weight[i]
                heappush(d,[dist[j],j])
            i = ne[i] 
    if dist[n*n]==I_max:
        return -1
    else:
        return dist[n*n]
for i in range(n):#先统计每一行
    for j in range(n):
      for k in range(j+1,n):
        if s[i][k-1]>s[i][k]:
          add(i*n+j+1,i*n+k+1,1)
        else:
          add(i*n+k,i*n+k+1,1)
          break
for i in range(n):#再统计每一列
    for j in range(n):
      for k in range(j+1,n):
        if s[k-1][i]>s[k][i]:
          add(j*n+i+1,k*n+i+1,1)
        else:
          add((k-1)*n+i+1,k*n+i+1,1)
          break
print(dijkstra())

然后下面是正确题意版
注意此代码并非完全过题，此贴仅为个人记录
此代码可过50%数据，剩余50%，出现段错误，存不下了
在python中，测试如下，1e6~3e6，不出现段错误，大于此出现内存不够，段错误。
拿分万岁！

from heapq import *
n = int(input())
s = []
for i in range(n):
  ss=list(map(int,input().split()))
  s.append(ss)
I_max = float("inf")
N = 1000010
e = [0]*N
ne = [0]*N
ne[0]=-1
h = [0]*N
weight = [I_max]*N
idx = 0
dist = [I_max]*N#距离
IS = [0]*N
def add(x,y,z):
    global idx
    idx+=1
    e[idx] = y
    weight[idx] = z
    ne[idx] = h[x]
    h[x] = idx
def dijkstra():
    dist[1]=0
    d = []
    heappush(d,[0,1])
    while d:
        t = heappop(d)
        ver = t[1]
        if IS[ver]:
            continue
        IS[ver] = 1
        distance = t[0]
        i = h[ver]
        while i!=-1:
            j = e[i]
            if distance+weight[i]<dist[j]:
                dist[j] = distance+weight[i]
                heappush(d,[dist[j],j])
            i = ne[i] 
    if dist[n*n]==I_max:
        return -1
    else:
        return dist[n*n]
for i in range(n):#先从左到右统计每一行
    for j in range(n):
      for k in range(j+1,n):
        if s[i][k-1]>s[i][k]:
          add(i*n+j+1,i*n+k+1,1)
        else:
          add(i*n+k,i*n+k+1,1)
          break
for i in range(n):#再从右到左统计每一行
    for j in range(n-1,0,-1):#最多到1即可
      for k in range(j-1,-1,-1):#此处到0
        if s[i][k+1]>s[i][k]:
          add(i*n+j+1,i*n+k+1,1)
        else:
          add(i*n+k,i*n+k+1,1)
          break
for i in range(n):#再(r,c)可以到(r+1,c)
    for j in range(n-1):
        add(j*n+i+1,(j+1)*n+i+1,1)
print(dijkstra())