hdu 5636 搜索 BestCoder Round #74 (div.2)

Shortest Path

Accepts: 40

Submissions: 610

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

问题描述

有一条长度为 $n$ 的链. 节点 $i$ 和 $i + 1$ 之间有长度为 $1$ 的边. 现在又新加了3条边, 每条边长度都是1. 给出 $m$ 个询问, 每次询问两点之间的最短路.

输入描述

输入包含多组数据. 第一行有一个整数 $T$ , 表示测试数据的组数. 对于每组数据:

第一行包含2个整数 $n$ 和 $m$   $10^5)$ 表示节点的数目和询问数目. 接下来一行包含 $6$ 个有空格分开的整数 $a_1, b_1, a_2, b_2, a_3, b_3$   $a_1,a_2,a_3,b_1,b_2,b_3 le n)$ , 表示新加的三条边为 $(a_1,b_1)$ ,  $(a_2,b_2)$ ,  $(a_3,b_3)$ . 接下来 $m$ 行, 每行包含两个整数 $s_i$ 和 $t_i$   $s_i, t_i le n)$ , 表示一组询问.

所有数据中 $m$ 的和不超过 $10^6$ .

输出描述

对于每组数据, 输出一个整数 $S=(displaystylesum_{i=1}^{m} i cdot z_i) ext{ mod } (10^9 + 7)$ , 其中 $z_i$ 表示第 $i$ 组询问的答案.

输入样例

1
10 2
2 4 5 7 8 10
1 5
3 1

输出样例

/*
hdu 5636 搜索 BestCoder Round #74 (div.2)

给你一条链，每两个节点之间的距离是1，然后加上3条边。
m个询问，[l,r]之间的最短路

表示最开始想的是每个询问查找一次最小值，但是思路还是有问题，准确的说只有3
条捷径会对最后的答案造成影响。所以每次我们只需要枚举走过捷径的数目以及进入
的位置，找出最小值即可。


正解：
通过搜索，可以找出走3条捷径的所有情况，然后取出最小值即可

hhh-2016-03-05 21:43:51;
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define MID(a,b) (a+((b-a)>>1))
const int maxn=100005;
const int MOD = 1e9+7;

int tx[5],ty[5];
int vis[5],l,r;
ll ans ;

void fin(int now,ll len)
{
    if(len+abs(r-now)<ans) ans = (ll)(len+abs(r-now))%MOD;
    for(int i =1;i <= 3;i++)
    {
        if(!vis[i])
        {
            vis[i] = 1;
            fin(tx[i],abs(len+abs(ty[i]-now))+1);
            fin(ty[i],abs(len+abs(tx[i]-now))+1);
            vis[i] = 0;
        }
    }
}

int main()
{
    int t,n,q;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&q);
        for(int i =1;i <= 3;i++)
        {
            scanf("%d%d",&tx[i],&ty[i]);
        }
        ll sum = 0;
        for(int i =1;i <= q;i++)
        {
            scanf("%d%d",&l,&r);
            ans = abs(l-r);
            fin(l,0);
            sum=(ll)(sum+(ll)(ans*i)%MOD)%MOD;
//            cout << ans <<endl;
        }
        printf("%I64d
",sum%MOD);
    }
    return 0;
}