之前想了一种枚举方法， 结果比赛完后没过终测， 题解的方法是这样的， 对于新加的六个边我们新建一个图， 用floyd跑出每两个点之间的最短路径， 在计算l - r的距离的时候我们就可以枚举36种可能求出最优解即可。代码如下：
#include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <cmath> #include <iostream> using namespace std; typedef long long LL; int n, m; int a[10]; int d[10][10]; int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &m); for(int i=1; i<=6; i++) scanf("%d", &a[i]); for(int i=1; i<=6; i++) for(int j=1; j<=6; j++) d[i][j] = abs(a[i]-a[j]); if(a[1]!=a[2]) d[1][2] = d[2][1] = 1; if(a[3]!=a[4]) d[3][4] = d[4][3] = 1; if(a[5]!=a[6]) d[5][6] = d[6][5] = 1; for(int k=1; k<=6; k++) for(int i=1; i<=6; i++) for(int j=1; j<=6; j++) d[i][j] = min(d[i][j], d[i][k]+d[k][j]); LL res = 0; for(int i=1; i<=m; i++) { int l, r; scanf("%d%d", &l, &r); LL dis = abs(r-l); for(int u=1; u<=6; u++) for(int v=1; v<=6; v++) dis = min(dis, (LL)abs(a[u]-l)+d[u][v]+abs(r-a[v])); res = (res+dis*i)%(1000000000+7); } cout<<res<<endl; } return 0; }