[原创]hdu 5636 &&bestcoder #74 1002 Shortest Path [floyd+松弛]【图论+思维】

# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

# define abs(x) (((x)>0)?(x):-(x))

const int N   = 1e5+10;
const int MOD = 1e9+7;
const int INF = 11111;

/******************************************/

int a[10],n,m;
int b[11][11];
int main(){
    int _;scanf("%d",&_);
    while(_--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=6;i++)scanf("%d",&a[i]);
        LL ans=0;

        for(int i=1;i<=6;i++)
            for(int j=1;j<=6;j++)
                b[i][j]=abs(a[i]-a[j]);
        
        b[1][2]=b[3][4]=b[5][6]=1;
        b[2][1]=b[4][3]=b[6][5]=1;

        for(int k=1;k<=6;k++)
            for(int i=1;i<=6;i++)
                for(int j=1;j<=6;j++)
                    if(b[i][j]>b[i][k]+b[k][j])
                        b[i][j]=b[i][k]+b[k][j];
        
        for(LL o=1;o<=m;o++){
            scanf("%d%d",&a[7],&a[8]);
            int dis=abs(a[7]-a[8]);

            for(int i=1;i<=6;i++)
                for(int j=1;j<=6;j++){
                    int t=abs(a[i]-a[7])+b[i][j]+abs(a[j]-a[8]);
                    if(t<dis) dis=t;
                }
            
            ans+=o*dis;
            ans%=MOD;
        }
        printf("%lld\n",ans);
    }
    return 0;
}