Shortest Path
Accepts: 40
Submissions: 610
Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 131072/131072 K (Java/Others)
问题描述
有一条长度为nn的链. 节点ii和i+1i+1之间有长度为11的边. 现在又新加了3条边, 每条边长度都是1. 给出mm个询问, 每次询问两点之间的最短路.
输入描述
输入包含多组数据. 第一行有一个整数TT, 表示测试数据的组数. 对于每组数据: 第一行包含2个整数nn和mm (1 \le n,m \le 10^5)(1≤n,m≤105)表示节点的数目和询问数目. 接下来一行包含66个有空格分开的整数a_1, b_1, a_2, b_2, a_3, b_3a1,b1,a2,b2,a3,b3 (1 \le a_1,a_2,a_3,b_1,b_2,b_3 \le n)(1≤a1,a2,a3,b1,b2,b3≤n), 表示新加的三条边为(a_1,b_1)(a1,b1), (a_2,b_2)(a2,b2), (a_3,b_3)(a3,b3). 接下来mm行, 每行包含两个整数s_isi和t_iti (1 \le s_i, t_i \le n)(1≤si,ti≤n), 表示一组询问. 所有数据中mm的和不超过10^6106.
输出描述
对于每组数据, 输出一个整数S=(\displaystyle\sum_{i=1}^{m} i \cdot z_i) \text{ mod } (10^9 + 7)S=(i=1∑mi⋅zi) mod (109+7), 其中z_izi表示第ii组询问的答案.
输入样例
1
10 2
2 4 5 7 8 10
1 5
3 1
输出样例
7
思路：因为在每加入这些边之前我们知道任意两点最短距离是abs（a-b）；
那么我们每次要询问两个点之间的最短路，所以我们可以把新加的边和询问的边中两个点拿出来离散化下
然后建图加边，然后直接最短路即可，复杂度为O(m*8*8)。
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<stdlib.h>
5 #include<string.h>
6 #include<map>
7 using namespace std;
8 typedef long long LL;
9 int flag[10];
10 const LL N=1e9+7;
11 int cmp(const void*p,const void*q);
12 typedef struct pp
13 {
14 LL x;
15 int id;
16 }ss;
17 ss aa[10];
18 LL d[10];LL ma[10][10];
19 LL num[10];LL bum[10];
20 void dij(int n,int ans);
21 int main(void)
22 {
23 LL i,j,k,p,q;
24 scanf("%lld",&k);
25 while(k--)
26 {
27 scanf("%lld %lld",&p,&q);
28 for(i=0;i<6;i++)
29 {
30 scanf("%lld",&num[i]);
31 }LL sum=0;LL a=0;
32 while(q--)
33 { a++;
34 scanf("%lld %lld",&num[6],&num[7]);
35 LL ans=1;
36 for(i=0;i<8;i++)
37 {
38 aa[i].x=num[i];
39 aa[i].id=i;
40 }qsort(aa,8,sizeof(ss),cmp);
41 bum[aa[0].id]=1;
42 for(i=1;i<8;i++)
43 {
44 if(aa[i].x!=aa[i-1].x)
45 ans++;
46 bum[aa[i].id]=ans;
47 }
48 for(i=0;i<10;i++)
49 {
50 for(j=0;j<10;j++)
51 {
52 ma[i][j]=N;
53 }
54 }
55 ma[bum[0]][bum[1]]=ma[bum[1]][bum[0]]=1;
56 ma[bum[2]][bum[3]]=ma[bum[3]][bum[2]]=1;
57 ma[bum[4]][bum[5]]=ma[bum[5]][bum[4]]=1;
58 for(i=0;i<8;i++)
59 {
60 for(j=0;j<8;j++)
61 {
62 LL x=bum[i];
63 LL y=bum[j];
64 ma[x][y]=min(ma[x][y],abs(num[i]-num[j]));
65 }
66 }
67 dij(bum[6],ans);sum=(sum%N+d[bum[7]]*a%N)%N;
68 }printf("%lld\n",sum);
69 }return 0;
70 }
71
72 void dij(int n,int ans)
73 {
74 fill(d,d+10,N);
75 memset(flag,0,sizeof(flag));
76 d[n]=0;int i,j;
77 while(true)
78 {
79 int l=-1;
80 for(i=1;i<=ans;i++)
81 {
82 if((l==-1||d[l]>d[i])&&!flag[i])
83 {
84 l=i;
85 }
86 }if(l==-1)
87 break;
88 flag[l]=1;
89 for(i=1;i<=ans;i++)
90 {
91 d[i]=min(ma[l][i]+d[l],d[i]);
92 }
93 }
94 }
95 int cmp(const void*p,const void*q)
96 {
97 ss*n=(ss*)p;
98 ss*m=(ss*)q;
99 return n->x>m->x?1:-1;
100 }