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

2017-06-06 19:38:38 Tabris_ 阅读数：256

博客爬取于2020-06-14 22:40:04
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72886742

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5636
——————————————————————————————————————————

Shortest Path

Accepts: 40

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

Memory Limit: 131072/131072 K (Java/Others)
问题描述
有一条长度为n的链. 节点ii和i+1之间有长度为1的边. 现在又新加了3条边, 每条边长度都是1. 给出m个询问, 每次询问两点之间的最短路.
输入描述
输入包含多组数据. 第一行有一个整数T, 表示测试数据的组数. 对于每组数据:

第一行包含2个整数n和m$ (1 \le n,m \le 10^5)表示节点的数目和询问数目.接下来一行包含66个有空格分开的整数表示节点的数目和询问数目. 接下来一行包含66个有空格分开的整数a_1, b_1, a_2, b_2, a_3, b_3 (1 \le 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).接下来mm行,每行包含两个整数. 接下来mm行, 每行包含两个整数s_i和和t_i$(1≤si,ti≤n)(1 \le s_i, t_i \le n), 表示一组询问.

所有数据中mm的和不超过10^6106.
输出描述
对于每组数据, 输出一个整数S=(∑i=1mi⋅zi) mod (109+7)S=(\displaystyle\sum_{i=1}^{m} i \cdot z_i) \text{ mod } (10^9 + 7), 其中z_izi表示第ii组询问的答案.
输入样例
1
10 2
2 4 5 7 8 10
1 5
3 1
输出样例
7

——————————————————————————————————————————
首先对于给了N个节点求最短路 一定不能直接做了,

发现他加的三条边与查询的边一共就8个点,那么每次对这8个点写folyd不就好了,O(888)然而写了一发TLE

然后想这样怎么能在优化呢?

想到给定的那6个点是固定的,那么多次求就浪费了

然后考虑,让我查询的就一条边,那么其实也就是66条边对这条边松弛,那么复杂度就是O(66),

附本题代码
——————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# 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;
}