题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=5636
题解:
1、暴力枚举:
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;typedef long long LL;
const int maxn = 1e5 + ;
const int mod = 1e9 + ;int n, m;
int a[], b[];int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = ; i < ; i++) scanf("%d%d", a + i, b + i);
LL ans = ;
int x, y;
for (int i = ; i <= m; i++) {
scanf("%d%d", &x, &y);
//一条新路线都不走
int tmp = abs(x - y); //只走一条
for (int j = ; j < ; j++) {
tmp = min(tmp, abs(x - a[j]) + abs(b[j] - y) + );
tmp = min(tmp, abs(x - b[j]) + abs(a[j] - y) + );
} //走两条
for (int j = ; j < ; j++) {
for (int k = ; k < ; k++) {
if (j == k) continue;
//x -> j开头 -> j结尾 -> k开头 -> k结尾 -> y
tmp = min(tmp, abs(x - a[j]) + abs(b[j] - a[k]) + abs(b[k] - y) + );
//x -> j开头 -> j结尾 -> k结尾 -> k开头 -> y
tmp = min(tmp, abs(x - a[j]) + abs(b[j] - b[k]) + abs(a[k] - y) + );
//x -> j结尾 -> j开头 -> k开头 -> k结尾 -> y
tmp = min(tmp, abs(x - b[j]) + abs(a[j] - a[k]) + abs(b[k] - y) + );
//x -> j结尾 -> j开头 -> k结尾 -> k开头 -> y
tmp = min(tmp, abs(x - b[j]) + abs(a[j] - b[k]) + abs(a[k] - y) + );
}
} //走三条
for (int j = ; j < ; j++) {
for (int k = ; k < ; k++) {
if (j == k) continue;
for (int w = ; w < ; w++) {
if (w == j || w == k) continue;
tmp = min(tmp, abs(x - a[j]) + abs(b[j] - a[k]) + abs(b[k] - a[w]) + abs(b[w] - y) + );
tmp = min(tmp, abs(x - a[j]) + abs(b[j] - a[k]) + abs(b[k] - b[w]) + abs(a[w] - y) + );
tmp = min(tmp, abs(x - a[j]) + abs(b[j] - b[k]) + abs(a[k] - a[w]) + abs(b[w] - y) + );
tmp = min(tmp, abs(x - a[j]) + abs(b[j] - b[k]) + abs(a[k] - b[w]) + abs(a[w] - y) + ); tmp = min(tmp, abs(x - b[j]) + abs(a[j] - a[k]) + abs(b[k] - a[w]) + abs(b[w] - y) + );
tmp = min(tmp, abs(x - b[j]) + abs(a[j] - a[k]) + abs(b[k] - b[w]) + abs(a[w] - y) + );
tmp = min(tmp, abs(x - b[j]) + abs(a[j] - b[k]) + abs(a[k] - a[w]) + abs(b[w] - y) + );
tmp = min(tmp, abs(x - b[j]) + abs(a[j] - b[k]) + abs(a[k] - b[w]) + abs(a[w] - y) + );
}
}
}
ans += ((LL)i*tmp)%mod;
ans %= mod;
}
printf("%lld\n", ans);
}
return ;
}
2、floyd:
对三条新边对应的关键顶点重新建图,跑一遍floyd最短路,对于查询(xi,yi),我们枚举任意两个关键节点(aj,bj),求min(|xi-aj|+len+|bj-yi|),其中len表示新图里面aj到bj的最短距离。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL; const int maxn = 1e5 + ;
const int mod = 1e9 + ;
const int INF = 0x3f3f3f3f; int n, m;
int a[],mat[][]; void init() {
memset(mat, 0x3f, sizeof(mat));
for (int i = ; i < ; i++) mat[i][i] = ;
} int main() {
int tc;
scanf("%d", &tc);
while (tc--) {
init();
scanf("%d%d", &n, &m);
for (int i = ; i < ; i++) {
scanf("%d%d", a + i, a + i + );
}
//新图
for (int i = ; i < ; i++) {
for (int j = ; j < ; j++) {
mat[i][j] = abs(a[i] - a[j]);
}
}
for (int i = ; i < ; i++) {
mat[i][i + ] = mat[i + ][i] = ;
}
//floyd
for (int k = ; k < ; k++) {
for (int i = ; i < ; i++) {
for (int j = ; j < ; j++) {
mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
}
}
}
LL ans = ;
for (int i = ; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
LL z = abs(x-y);
//枚举所有情况
for (int i = ; i < ; i++) {
for (int j = ; j < ; j++) {
int tmp = abs(x - a[i]) + mat[i][j] + abs(a[j] - y);
z = min(z, (LL)tmp);
}
}
ans += z*i;
ans %= mod;
}
printf("%lld\n", ans);
}
return ;
}