【floyd】Shortest Path

传送门:【floyd】Shortest Path

题意:给你1—>n个点,每两个点距离是 1。再添加三条路,每条路的距离是1,先求最短路,然后用值去求题目所给的式子。

分析:可以用floyd多源最短路算法求这六个点之间的最短路,为什么呢?因为要求问的两个点之间的距离,那么这两个点之间的最小距离要么是它们的直接距离,要么就是过这六个点的两个,在用floyd算法就可以直接求出最短的。
也就是说假设求i到j的距离dis[i][j],我们应该尽可能通过那“三个边”,所以我们只需要枚举6个点当中的其中两个即可。
而这6个点之间任意两点最短路是可以求出的。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
 
const int maxn = 100005;
const int mod = 1e9+7;
int n,m,x[6],dis[6][6];
 
void floyd()
{
  for(int k = 0; k < 6; k++)
    for(int i = 0; i < 6; i++)
      for(int j = 0; j < 6; j++)
        dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
}
 
int main()
{
  int t,u,v;
  scanf("%d",&t);
  while(t--)
  {
    scanf("%d%d",&n,&m);
    for(int i = 0; i < 6; i++) //六个点
      scanf("%d",&x[i]);
    for(int i = 0; i < 6; i++)
      for(int j = 0; j < 6; j++)
        dis[i][j] = abs(x[i] - x[j]);
    for(int i = 0; i < 6; i += 2) //新加入的边
      dis[i][i+1] = dis[i+1][i] = 1;
    floyd();
    long long ans = 0;
    for(int i = 1; i <= m; i++)
    {
      scanf("%d%d",&u,&v);
      int len = abs(u - v);
      for(int j = 0; j < 6; j++)
        for(int k = 0; k < 6; k++)
        {
          int tmp = abs(u - x[j]) + abs(v - x[k]) + dis[j][k];
          len = min(len,tmp);
        }
      ans = (ans + (long long) i * len % mod) % mod;
    }
    printf("%lld\n",ans);
  }
  return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

1 × 4 =