记录编号	37770	评测结果	AAAAAA
题目名称	[BJOI2006] 狼抓兔子	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.487 s
提交时间	2012-04-07 18:55:10	内存使用	30.83 MiB

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#include <cstring>
#include <utility>
using namespace std;
const int MAXN=1000*1000+100;
const int INF=~0U>>1;
vector<int> Map[MAXN];
vector<int> Val[MAXN];
queue<int> Q;
int dist[MAXN];
int flag[MAXN];
int N,M,Source,Sink;
priority_queue<pair<int,int> > PQ;
inline void SP()
{
    for(int i=0;i<=Sink;i++) {flag[i]=0,dist[i]=INF;}
    dist[Source]=0;
    PQ.push(make_pair(0,Source));
    int u,v,cost;
    while(!PQ.empty())
    {
        u=PQ.top().second;
		if(u==Sink) {printf("%d\n",-PQ.top().first);return;}
        PQ.pop();
        if(!flag[u])
        {
            flag[u]=1;
            for(unsigned int i=0;i<Map[u].size();i++)
            {
                v=Map[u][i];
                cost=Val[u][i];
                if(!flag[v]&&dist[v]-dist[u]>cost)
                {
                    dist[v]=dist[u]+cost;
                    PQ.push(make_pair(-dist[v],v));
                }
            }
        }
    }
	printf("%d\n",dist[Sink]);
}
  
void AddEdge(int s,int e,int f)
{
    Map[s].push_back(e);
    Val[s].push_back(f);
    Map[e].push_back(s);
    Val[e].push_back(f);
}
  
void init()
{
    int x;
    scanf("%d %d\n",&N,&M);
     
    if(N==1 || M==1)
    {
        int Ans=INF,x;
        if(N==1)
        {
            for(int i=1;i<=M-1;i++)
            {
                scanf("%d",&x);
                if(x<Ans) Ans=x;
            }
            printf("%d\n",Ans);
        }
        else
        {
            for(int i=1;i<=N-1;i++)
            {
                scanf("%d\n",&x);
                if(x<Ans) Ans=x;
            }
            printf("%d\n",Ans);
        }
        return;
    }
     
    Source=0,Sink=(N-1)*(M-1)*2+1;
    /*以下橫向道路*/
    for(int i=1;i<=M-1;i++) { scanf("%d",&x); AddEdge(Source,2*i,x); }
    for(int i=2;i<=N-1;i++)
        for(int j=1;j<=M-1;j++) { scanf("%d",&x); AddEdge((i-2)*(M-1)*2+(j-1)*2+1,(i-1)*(M-1)*2+j*2,x);}
    for(int i=1;i<=M-1;i++) {scanf("%d",&x); AddEdge(Sink,(N-2)*(M-1)*2+i*2-1,x); }
    /*以下縱向道路*/
    for(int i=1;i<=N-1;i++)
    {
        scanf("%d",&x); AddEdge(Sink,(i-1)*(M-1)*2+1,x);
        for(int j=2;j<=M-1;j++)  { scanf("%d",&x); AddEdge((i-1)*(M-1)*2+(j-1)*2,(i-1)*(M-1)*2+(j-1)*2+1,x); }
        scanf("%d",&x); AddEdge(Source,i*(M-1)*2,x);
    }
    /*以下斜向道路*/
    for(int i=1;i<=N-1;i++)  for(int j=1;j<=M-1;j++)
    {
        scanf("%d",&x); AddEdge((i-1)*(M-1)*2+(j-1)*2+1,(i-1)*(M-1)*2+j*2,x);
    }
    SP();
}
  
int main()
{
    freopen("bjrabbit.in","r",stdin);
    freopen("bjrabbit.out","w",stdout);
    init();
    return 0;
}