首页 > 代码库 > [BZOJ 1001 狼抓兔子]
[BZOJ 1001 狼抓兔子]
平面图的对偶图转化,具体请看周冬大神的论文
建边时需稍微注意
下面是代码:
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #define N 1010 7 #define inf 0x7fffffff 8 using namespace std; 9 10 const int maxn=N*N*2,maxm=maxn*3;11 int n,m,s,t,p,d,p1,p2;12 int head[maxn],go[maxm],next[maxm],w[maxm];13 14 void build(int a,int b,int c)15 {16 go[++p]=b;17 next[p]=head[a];18 w[p]=c;19 head[a]=p;20 }21 22 void Double_build(int a,int b,int c)23 {24 build(a,b,c);25 build(b,a,c);26 }27 28 int num(int a,int b){return (((a-1)*(m-1)+b)*2);}29 30 int que[maxn],lead,tail,use[maxn],dis[maxn],node;31 32 void spfa()33 {34 memset(use,0,sizeof use);35 for (int i=s;i<=t;i++) dis[i]=inf;36 lead=tail=1;que[1]=s;use[s]=1;dis[s]=0;37 for (;lead<=tail;lead++,use[node]=0)38 {39 node=que[lead%maxn];40 for (int i=head[node];i;i=next[i]) if (dis[go[i]]>dis[node]+w[i])41 {42 dis[go[i]]=dis[node]+w[i];43 if (!use[go[i]])44 {45 use[go[i]]=1;46 que[(++tail)%maxn]=go[i];47 }48 }49 }50 }51 52 int main()53 {54 scanf("%d%d",&n,&m);55 s=1;t=(n-1)*m*2;56 for (int i=1;i<=n;i++)57 for (int j=1;j<m;j++)58 {59 scanf("%d",&d);60 p1=i==1?t:num(i-1,j)+1;p2=i==n?s:num(i,j);61 Double_build(p1,p2,d);62 }63 for (int i=1;i<n;i++)64 for (int j=1;j<=m;j++)65 {66 scanf("%d",&d);67 p1=j==1?s:num(i,j-1);p2=j==m?t:num(i,j)+1;68 Double_build(p1,p2,d);69 }70 for (int i=1;i<n;i++)71 for (int j=1;j<m;j++)72 {73 scanf("%d",&d);74 p1=num(i,j);p2=p1+1;75 Double_build(p1,p2,d);76 }77 spfa();78 printf("%d",dis[t]);79 return 0;80 }
[BZOJ 1001 狼抓兔子]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。