题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5636
题意：给我们一条n个点组成的链，然后在上面加3条边，输出某两个点
题目一看就是最短路问题，但是一看点数：10^5，比赛的时候还真的没敢去做，觉得这题要算出所有点到其他点的最短距离，无论用Floyd还是SPFA都应该会炸时间，事后才发现并不需要求出所有点之间的距离，只需要求出加三条边的那6个点到其他点的距离，因为u，v两点的距离如果没有经过这加的三条边就是v-u，如果经过了就是这三条边的6个端点到u和v的距离和。
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100000+5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
int a[6],dis[6][maxn],res[maxn];
bool vis[maxn];
vector<int> G[maxn];
int n,m;
void addEdge(int u,int v)
{G[u].push_back(v);G[v].push_back(u);
}
void SPFA(int i,int s)
{memset(dis[i],INF,sizeof(dis[i]));memset(vis,false,sizeof(vis));dis[i][s] = 0;vis[s] = true;queue<int> q;q.push(s);while(!q.empty()){int u = q.front();q.pop();for(int j=0; j<G[u].size(); j++){int v = G[u][j];if(vis[v]) continue;dis[i][v] = dis[i][u]+1;vis[v] = true;q.push(v);}}
}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=1; i<=n; i++)G[i].clear();for(int i=1; i<n; i++)addEdge(i,i+1);for(int i=0; i<3; i++){int u,v;scanf("%d%d",&u,&v);addEdge(u,v);a[i*2] = u;a[i*2+1] = v;}for(int i=0; i<6; i++)SPFA(i,a[i]);for(int i=0; i<m; i++){int u,v;scanf("%d%d",&u,&v);if(u > v) swap(u,v);res[i] = v-u;for(int j=0; j<6; j++)res[i] = min(res[i],dis[j][u]+dis[j][v]);}int ans = 0;for(int i=0; i<m; i++)ans = (ans + 1ll*(i+1)*res[i]) % MOD;printf("%d\n",ans);}return 0;
}