哈哈哈哈，我就知道这道题目再扔给我，我还是不会，就是这么菜，哈哈哈
一开始官方题解就没搞懂…然后就看了一下别人的代码，水水过就算了。今天拿到…GG；
题意：
一开始，有一张原图，有一条长度为n的链. 节点i和i+1之间有长度为1的边.
现在又新加了3条边, 每条边长度都是1. 给出m个询问, 每次询问两点之间的最短路.
然后让你算出对于每组数据, 输出一个整数S=(∑i=1mi⋅zi) mod (109+7), 其中zi表示第i
组询问的答案.
官方题解：
你可以选择分类讨论, 但是估计可能会写漏一些地方. 只要抽出新增边的端点作为关键点, 建立一个新图, 然后跑一遍floyd就好了. 复杂度大概O(6^2⋅m)
然后继续摸着摸着发现，也可以说是感觉到。
我们在一个用领接矩阵所存储的图中，求一个点到一个点的最短距离，无非就是min(两点间直接多长，点1经过一些最短路到达点2)；
这一题让我体会很多：
第一：
利用一个图来进行操作，那么无可厚非这个图里面点之间的距离就是最短距离。建图啊建图，这只是个初始化的过程，在第二遍拿起这道题的时候还是错了。
第二：
利用图这个过程，那么就是经过与不经过的问题；还有这道题目让我体会最深的就是怎么经过，在纸上画了一下，瞬间爆炸，我floyd的精华一点都不知道啊！
过程，过程！！！
这道题目显示了自己：1,基础差！ 2,floyd算法没理解！还是太菜，太菜。
#include<cstdio>
#include<stdlib.h>
#include<string.h>
#include<iostream>
using namespace std;
typedef long long LL;
LL mod=1e9+7;
LL INF=0x3f3f3f3f;
int n;
LL bmap[10][10];
LL cp[110];
void init()
{
for(int i=0; i<6; i++)
{
for(int j=0; j<6; j++)
{
bmap[i][j]=bmap[j][i]=abs(cp[i]-cp[j]);
}
}
}
void debug()
{
for(int i=0; i<6; i++)
{
for(int j=0; j<6; j++)
printf("%d ",bmap[i][j]);
printf("
");
}
}
void floyd()
{
int k,i,j;
for(k=0; k<6; k++)
{
for(i=0; i<6; i++)
{
for(j=0; j<6; j++)
{
bmap[i][j]=min(bmap[i][j],bmap[i][k]+bmap[k][j]);
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int num;
scanf("%d%d",&n,&num);
for(int i=0; i<6; i++)
{
scanf("%d",&cp[i]);
}
init();
bmap[0][1]=bmap[1][0]=1;
bmap[2][3]=bmap[3][2]=1;
bmap[4][5]=bmap[5][4]=1;
//建图,要想在一张图上进行操作，则所必须的就是保证这张图就是最完美（最短路）的图，所以跑一下floyd；
floyd();
// debug();
LL ans=0;
for(int p=1; p<=num; p++)
{
int u,v;
scanf("%d%d",&u,&v);
LL sum=abs(u-v);
for(int i=0; i<6; i++)
{
for(int j=0; j<6; j++) //跑一跑最短路
{
sum=min(sum,abs(u-cp[i])+abs(v-cp[j])+bmap[i][j]);
sum=min(sum,abs(v-cp[i])+abs(u-cp[j])+bmap[i][j]);
}
}
ans=(ans+(p*sum)%mod)%mod;
}
printf("%lld
",ans);
}
return 0;
}