spfa的话复杂度O(km*n)，k为常数。

```#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1003;
const int M = 2000005;
const int inf = 0x3f3f3f3f;
struct node
{
int to,next,val;
}g[M + M];
int m,n,nm,num;
int dis[M],que[M];
bool flag[M];
{
g[num].to = e;
g[num].val = v;
}
int nextint()
{
int ret;
char c;
while((c = getchar()) > '9' || c < '0')
;
ret = c - '0';
while((c = getchar()) >= '0' && c <= '9')
ret = ret * 10 + c - '0';
return ret;
}
void build()
{
scanf("%d",&m);
nm = (n * m - m - n + 1)<<1;//there are nm nodes in new graph except s and t;
int i,j,tmp;
num = 0;

for(j = 1;j < m;j ++)//
{
scanf("%d",&tmp);
}
for(i = 1;i < n - 1;i ++)
{
for(j = 1;j < m;j ++)
{
scanf("%d",&tmp);
add((i<<1)* (m - 1) + j,((i<<1) - 1) * (m - 1) + j,tmp);
}
}
for(j = 1;j < m;j ++)
{
scanf("%d",&tmp);
add(0,((n<<1)-3) * (m - 1) + j,tmp);
}

for(i = 0;i < n - 1;i ++)
{
for(j = 1;j <= m;j ++)
{
scanf("%d",&tmp);
if(j == 1)
else if(j == m)
else
add((i<<1)*(m  - 1) + j - 1,(i<<1)*(m - 1) + j + m - 1,tmp);
}
}

for(i = 0;i < n - 1;i ++)
{
for(j = 1;j < m;j ++)
{
scanf("%d",&tmp);
add((i<<1|1)*(m - 1) + j,(i<<1)*(m - 1) + j,tmp);
}
}
}
void SPFA()
{
int i,front,rear;
memset(flag,false,sizeof(flag));
memset(dis,0x3f,sizeof(dis));
front = rear = dis[0] = 0;
que[rear ++] = 0;
flag[0] = true;
while(front != rear)
{
int u = que[front ++];
flag[u] = false;
if(front == M)
front = 0;
for(int i = head[u];~i;i = g[i].next)
{
int v = g[i].to;
if(dis[v] > dis[u] + g[i].val)
{
dis[v] = dis[u] + g[i].val;
if(flag[v] == false)
{
flag[v] = true;
que[rear ++] = v;
if(rear == M)
rear = 0;
}
}
}
}
}
void solve()
{
SPFA();
printf("%d\n",dis[nm + 1]);
}
int main()
{
while(scanf("%d",&n) != EOF)
{
build();
solve();
}
return 0;
}
//73072 kb  3688 ms
```