6176 电流损耗计算

经验值：3200

时间限制：1000毫秒

内存限制：128MB

题目描述 Description

现在有一个 n∗m的电路板。在每一个位置都有一个电阻， (i,j)这个位置的电阻值为 R ij ​ 。 现在在 (1,a)位置有一个电源，往电路板供电，在 (n,b)和 (n,c)上各有一个电子元件。 已知电流在电路板上会朝上下左右 4 4个方向流东，并且会选择电阻最小的路径。现在请求出，给两个电子元件供电，路径上最少要经过的电阻之和。

输入描述 Input Description

第一行，n m a b c

接下来n行，每行m个整数，第i行第j列表示Rij

输出描述 Output Description

最小的电阻之和

样例输入 Sample Input 5 5 1 2 4

1 8 1 6 6

1 1 1 2 4

8 3 1 2 2

1 2 1 9 1

1 0 9 1 1

样例输出 Sample Output

15

数据范围及提示 Data Size & Hint 0<n,m≤100，0≤Rij≤10^9，0<a,b,c≤m

---

#include<bits/stdc++.h>
using namespace std;
struct node{int x,y;};
vector<node>g[105][105],pre[105][105];
int n,m,f[105][105],vis[105][105],a,b,c,dir[4][2]={{1},{-1},{0,1},{0,-1}};
long long sum,dis[105][105],minsum=1e18;
bool fd(int x,int y,int x2,int y2){
	if(x<1||x>n||x2<1||x>n||y<1||y>m||y2<1||y2>m)return 0;
	for(int i=0;i<pre[x2][y2].size();i++)if(pre[x2][y2][i].x==x&&pre[x2][y2][i].y==y)return 1; 
	return 0;
}
void add(int x,int y,int x2,int y2,int t,bool b1,bool b2){
	if(b1==0){
		sum+=f[x][y]*t;
		return; 
	}
	if(b2==0){
		sum+=f[x2][y2]*t;
		return;
	}
	if(x==x2&&y==y2)sum+=f[x][y]*t;
	else sum+=(f[x][y]+f[x2][y2])*t;
}
void dfs(int x,int y,int x2,int y2,bool b1,bool b2){
	if(vis[x][y]==1&&!b1||vis[x2][y2]==1&&!b2)return;
	add(x,y,x2,y2,1,b1,b2);
	vis[x][y]=vis[x2][y2]=1;
	if(x==n&&x2==n&&y==b&&y2==c){
		minsum=min(minsum,sum);
		add(x,y,x2,y2,-1,b1,b2);
		vis[x][y]=vis[x2][y2]=0;
		return;
	}else if(x==n&&y==b){
		for(int i=0;i<4;i++){
			int nx2=x2+dir[i][0],ny2=y2+dir[i][1];
			if(fd(x2,y2,nx2,ny2)){
				dfs(x,y,nx2,ny2,1,0);
			} 
		}
	}else if(x2==n&&y2==c){
		for(int i=0;i<4;i++){
			int nx=x+dir[i][0],ny=y+dir[i][1];
			if(fd(x,y,nx,ny)){
				dfs(nx,ny,x2,y2,0,1);
			} 
		}
	}else{
		for(int i=0;i<4;i++){
			int nx=x+dir[i][0],ny=y+dir[i][1];
			for(int j=0;j<4;j++){
				int nx2=x2+dir[j][0],ny2=y2+dir[j][1];
				if(fd(x,y,nx,ny)&&fd(x2,y2,nx2,ny2)){
					dfs(nx,ny,nx2,ny2,1,1);
				}
			}
		}
	}
	add(x,y,x2,y2,-1,b1,b2);
	vis[x][y]=vis[x2][y2]=0;
}
int main(){
	cin>>n>>m>>a>>b>>c;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>f[i][j];
			if(i!=1)g[i][j].push_back((node){i-1,j});
			if(i!=n)g[i][j].push_back((node){i+1,j});
			if(j!=1)g[i][j].push_back((node){i,j-1});
			if(j!=m)g[i][j].push_back((node){i,j+1});
		}
	}
	
	memset(dis,0x3f,sizeof(dis));
	dis[1][a]=f[1][a],vis[1][a]=1;
	int dx=1,dy=a;
	for(int i=1;i<n*m;i++){
		int posx=0,posy=0;
		long long minn=1e18;
		for(int j=0;j<g[dx][dy].size();j++){
			int vx=g[dx][dy][j].x,vy=g[dx][dy][j].y;
			if(dis[vx][vy]>dis[dx][dy]+f[vx][vy]){
				dis[vx][vy]=dis[dx][dy]+f[vx][vy];
				pre[vx][vy].clear(); 
				pre[vx][vy].push_back({dx,dy});
			}else if(dis[vx][vy]==dis[dx][dy]+f[vx][vy])pre[vx][vy].push_back({dx,dy});
		}
		for(int j=1;j<=n;j++){
			for(int k=1;k<=m;k++){
				if(dis[j][k]<minn&&vis[j][k]==0){
					minn=dis[j][k];
					posx=j,posy=k;
				}
			}
		}
		dx=posx,dy=posy;
		vis[dx][dy]=1;
	}
	memset(vis,0,sizeof(vis)); 
	dfs(1,a,1,a,0,0);
	cout<<minsum;
	return 0;
}