[TIOJ] 1034. 搶救雷恩大兵 (Saving Ryan)

題目連結:http://tioj.infor.org/problems/1034

---

本題N超小的，估了一下到$O(N^6)$甚至$O(N^7)$可能都會過，不過該怎麼做這題呢XD
仔細想想我們如果可以快速得到任意兩點的最短距離的話，那就直接枚舉炸掉所有位置，看看哪樣比較短，也就是說答案就是$\min\limits_{\forall k \in V} dis[a][k]+dis[k][b]-2 \times val[k]$(其中v是所有點的集合)(這是先把二維圖轉一維後的寫法)，而任兩點最短路徑的話就直接寫個floyd-warshall就好了XD
不過說直接floyd-warshall很容易，但本題給的是點權，可能沒辦法好好做，所以我直接用了一個小技巧(或許可以不用用拉XD):把a到b的距離設成$2 \times val[b]-val[a]$，最後算a到b時再加回$2 \times val[a]-val[b]$他的值就會是好的了

#include <bits/stdc++.h>
using namespace std;

typedef long long lld;
#define N 20
#define INF 100000

int g[N+5][N+5];
lld sg[3000][3000];
int n;

inline int Hash(int,int);

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&g[i][j]);
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int p=0;p<n;p++)for(int q=0;q<n;q++)sg[Hash(i,j)][Hash(p,q)]=INF;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			sg[Hash(i,j)][Hash(i,j)]=0;
			if(i-1>=0) sg[Hash(i,j)][Hash(i-1,j)]=2*g[i-1][j]-g[i][j];
			if(i+1< n) sg[Hash(i,j)][Hash(i+1,j)]=2*g[i+1][j]-g[i][j];
			if(j-1>=0) sg[Hash(i,j)][Hash(i,j-1)]=2*g[i][j-1]-g[i][j];
			if(j+1< n) sg[Hash(i,j)][Hash(i,j+1)]=2*g[i][j+1]-g[i][j];
		}
	}
	for(int k1=0;k1<n;k1++)for(int k2=0;k2<n;k2++)for(int i1=0;i1<n;i1++)for(int i2=0;i2<n;i2++)for(int j1=0;j1<n;j1++)for(int j2=0;j2<n;j2++) sg[Hash(i1,i2)][Hash(j1,j2)]=min(sg[Hash(i1,i2)][Hash(j1,j2)], sg[Hash(i1,i2)][Hash(k1,k2)]+sg[Hash(k1,k2)][Hash(j1,j2)]);
	int q;
	scanf("%d",&q);
	while(q--){
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		x1--,y1--,x2--,y2--;
		lld ans=INF;
		for(int k1=0;k1<n;k1++)for(int k2=0;k2<n;k2++) ans=min(ans, sg[Hash(x1,y1)][Hash(k1,k2)]+(2*g[x1][y1]-g[k1][k2])+sg[Hash(k1,k2)][Hash(x2,y2)]+(2*g[k1][k2]-g[x2][y2])-2*g[k1][k2]);
		printf("%lld\n",ans);
	}
	return 0;
}

inline int Hash(int x,int y){
	return x*100+y;
}