http://wenku.baidu.com/view/8f1fde586edb6f1aff001f7d.html
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
#define N 1001
int n,m,S,T,nn;
struct Point{int u,d;};
bool operator < (Point a,Point b){return a.d>b.d;}
int dis[N*N*2+2];
bool vis[N*N*2+2];
priority_queue<Point>q;
int en,v[N*N*3*2],next[N*N*3*2],w[N*N*3*2],first[N*N*2+2];
void AddEdge(int U,int V,int W)
{
v[++en]=V;
w[en]=W;
next[en]=first[U];
first[U]=en;
}
void dijkstra()
{
memset(dis+1,0x7f,sizeof(int)*(nn));
dis[S]=0; q.push((Point){S,0});
while(!q.empty())
{
int U=q.top().u; q.pop();
if(!vis[U])
{
vis[U]=1;
for(int i=first[U];i;i=next[i])
if((ll)dis[v[i]]>(ll)dis[U]+(ll)w[i])
{
dis[v[i]]=dis[U]+w[i];
q.push((Point){v[i],dis[v[i]]});
}
}
}
}
int main()
{
int x;
scanf("%d%d",&n,&m); nn=(n-1)*(m-1)*2+2; S=nn-1; T=nn;
for(int j=1;j<m;++j)
{
scanf("%d",&x);
AddEdge(S,j,x);
AddEdge(j,S,x);
}
for(int i=2;i<n;++i)
for(int j=1;j<m;++j)
{
scanf("%d",&x);
AddEdge(((i<<1)-3)*(m-1)+j,((i<<1)-2)*(m-1)+j,x);
AddEdge(((i<<1)-2)*(m-1)+j,((i<<1)-3)*(m-1)+j,x);
}
for(int j=1;j<m;++j)
{
scanf("%d",&x);
AddEdge(((n<<1)-3)*(m-1)+j,T,x);
AddEdge(T,((n<<1)-3)*(m-1)+j,x);
}
for(int i=1;i<n;++i)
{
scanf("%d",&x);
AddEdge(T,((i<<1)-1)*(m-1)+1,x);
AddEdge(((i<<1)-1)*(m-1)+1,T,x);
for(int j=2;j<m;++j)
{
scanf("%d",&x);
AddEdge(((i<<1)-2)*(m-1)+j-1,((i<<1)-1)*(m-1)+j,x);
AddEdge(((i<<1)-1)*(m-1)+j,((i<<1)-2)*(m-1)+j-1,x);
}
scanf("%d",&x);
AddEdge(((i<<1)-1)*(m-1),S,x);
AddEdge(S,((i<<1)-1)*(m-1),x);
}
for(int i=1;i<n;++i)
for(int j=1;j<m;++j)
{
scanf("%d",&x);
AddEdge(((i<<1)-2)*(m-1)+j,((i<<1)-1)*(m-1)+j,x);
AddEdge(((i<<1)-1)*(m-1)+j,((i<<1)-2)*(m-1)+j,x);
}
dijkstra();
printf("%d
",dis[T]);
return 0;
}