太离谱了，我把这题做成带堆优化的spfa，可能不是spfa。最后靠着吸氧过去。果然stl和O2绝配。 有没有dalao帮蒟蒻优化下，看不用吸氧过得去吗。 谢谢dalao.

#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=1e3+5;
int map[maxn][maxn],vis[maxn][maxn],book[maxn][maxn];//vis是保存最大值的最小值用的
int dix[4]={-1,0,1,0},diy[4]={0,1,0,-1};
struct node{
	int minn,x,y;
};
struct cmp{
	bool operator()(const node a,const node b){
		return a.minn>b.minn;
	}
};
priority_queue<node,vector<node>,cmp>pq;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
int main()
{
	int n,m,ans=0x7fffffff;
	cin>>n>>m;
	rep(i,1,n)
		rep(j,1,m)
			map[i][j]=read();
	rep(i,1,m)pq.push(node{map[2][i],2,i}),vis[2][i]=map[2][i];
	while(!pq.empty())
	{
		int x=pq.top().x,y=pq.top().y,mn=pq.top().minn;
		pq.pop();
		book[x][y]=0;
		if(x==n){
			ans=min(ans,mn);
			continue;
		}
		if(vis[x][y]<mn)continue;//可以发现要是vis[x][y]比较小就可以不用将这个点再扩展，之前已经扩展过了
		rep(i,0,3){
			int x0=x+dix[i],y0=y+diy[i];
			if(x0>1&&x0<=n&&y0>=1&&y0<=m)
				if(!vis[x0][y0]||(mn<vis[x0][y0]&&map[x0][y0]<vis[x0][y0])){
					vis[x0][y0]=max(mn,map[x0][y0]);
					if(!book[x0][y0])pq.push({vis[x0][y0],x0,y0}),book[x0][y0]=1;
				} 
		}
	}
	cout<<ans<<endl;
}