题目：Animal Run
题意：
有一群动物想从网格图的起点（左上角）跑到终点（右下角）。
这张网格图的每一条边都有一个正整数的权值，代表拦截这条边所需的人数。
现在要求出最少需要多少人拦截，才能使动物无法跑到终点。
思路：
把每一个三角形的面当做节点，并从左到右编号，即每一个节点（x,y）的编号为(x-1)*(2*(m-1))+y （数组从1开始编号）。
对于两个相邻的三角形，在它们之间连上一条边，权值为其在网格图中公共边的权值。
令起点的id为0，终点的id为(n-1)*(2*(m-1))+m+1，可以看做点（n，m+1）。
把所有和网格图左或下边界相接的面和起点相连，和右或上边界相连的点和终点相连。此时要注意右上角和左下角的面要连两次。
这时可以看出，从起点到终点的任何一条路径都可以把图割成不连通的两块，所以只用从起点到终点跑一遍最短路就可以了。
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 2000000struct Pair {int x,y;Pair(int xx=0,int yy=0) {x=xx,y=yy;}bool operator < (const Pair& oth) const {return y>oth.y||(y==oth.y&&x<oth.x);}
};int n,m;
int e;vector<Pair> a[maxn+5];priority_queue<Pair> p;
bool c[maxn+5]= {0};
int dist[maxn+5]= {0};int getid(int x,int y) {return (x-1)*(2*(m-1))+y;
}void init() {for(int i=0; i<=maxn+2; i++) a[i].clear();memset(c,0,sizeof(c));for(int i=0; i<=maxn+2; i++) dist[i]=(1<<28);priority_queue<Pair> emp;p=emp;
}void readin() {e=getid(n-1,(m-1)*2+1);for(int i=1; i<=n; i++) {for(int j=1; j<m; j++) {int z;scanf("%d",&z);if(i==1) {a[getid(i,j*2)].push_back(Pair(e,z));} else if(i==n) {a[0].push_back(Pair(getid(i-1,j*2-1),z));} else {a[getid(i-1,j*2-1)].push_back(Pair(getid(i,j*2),z));a[getid(i,j*2)].push_back(Pair(getid(i-1,j*2-1),z));}}}for(int i=1; i<n; i++) {for(int j=1; j<=m; j++) {int z;scanf("%d",&z);if(j==1) {a[0].push_back(Pair(getid(i,j*2-1),z));} else if(j==m) {a[getid(i,j*2-2)].push_back(Pair(e,z));} else {a[getid(i,j*2-1)].push_back(Pair(getid(i,j*2-2),z));a[getid(i,j*2-2)].push_back(Pair(getid(i,j*2-1),z));}}}for(int i=1; i<n; i++) {for(int j=1; j<m; j++) {int z;scanf("%d",&z);a[getid(i,2*j)].push_back(Pair(getid(i,2*j-1),z));a[getid(i,2*j-1)].push_back(Pair(getid(i,2*j),z));}}
}void dijkstra() {dist[0]=0;p.push(Pair(0,0));while(!p.empty()) {Pair x=p.top();p.pop();if(c[x.x]) continue;c[x.x]=true;for(int i=0; i<a[x.x].size(); i++) {if(dist[a[x.x][i].x]>x.y+a[x.x][i].y) {dist[a[x.x][i].x]=x.y+a[x.x][i].y;p.push(Pair(a[x.x][i].x,dist[a[x.x][i].x]));}}}
}void print(int& T) {printf("Case %d: Minimum = %d\n",++T,dist[e]);
}int main() {int T=0;while(~scanf("%d%d",&n,&m)&&n) {init();readin();dijkstra();print(T);}return 0;
}