记录编号	309323	评测结果	AAAAAAAAAA
题目名称	[NOI 2010]海拔	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.268 s
提交时间	2016-09-19 14:18:51	内存使用	44.50 MiB

#include<cstdio>
#include<algorithm>
#include<functional>
#include<queue>
using namespace std;
const int N=2000010,maxl=9999999;
struct edge{
	int f,t,l;
	edge(int F=0,int T=0,int L=0){f=F;t=T;l=L;}
}w[N];
int n,head[N],tail[N],next[N],cnt;
void add(int f,int t){
	w[++cnt]=edge(f,t,0);
	scanf("%d",&w[cnt].l);
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
}
int dis[N],s,t;bool vis[N];
inline int P(int x,int y){
	if (!x||y>n) return t;
	if (!y||x>n) return s;
	return (x-1)*n+y;
}
struct point{
	int p,d;
	point(int P){p=P;d=dis[p];}
	bool operator > (const point &x)const{return d>x.d;}
};
priority_queue<point,vector<point>,greater<point> > Q;
void dijsktra(){
	for (int i=s;i<=t;i++) dis[i]=maxl,vis[i]=0;
	dis[s]=0;Q.push(point(s));
	while (!Q.empty()){
		int v=Q.top().p;Q.pop();
		if (vis[v]) continue;vis[v]=1;
		if (v==t) break;
		for (int i=head[v];i;i=next[i])
		if (dis[w[i].t]>dis[v]+w[i].l){
			dis[w[i].t]=dis[v]+w[i].l;
			Q.push(point(w[i].t));
		}
	}
}
int main()
{
	freopen("altitude.in","r",stdin);
	freopen("altitude.out","w",stdout);
	scanf("%d",&n);
	s=0;t=n*n+1;
	for (int i=0;i<=n;i++)
	for (int j=1;j<=n;j++)
		add(P(i+1,j),P(i,j));
	for (int i=1;i<=n;i++)
	for (int j=0;j<=n;j++)
		add(P(i,j),P(i,j+1));
	for (int i=0;i<=n;i++)
	for (int j=1;j<=n;j++)
		add(P(i,j),P(i+1,j));
	for (int i=1;i<=n;i++)
	for (int j=0;j<=n;j++)
		add(P(i,j+1),P(i,j));
	dijsktra();
	printf("%d\n",dis[t]);
	return 0;
}