题目链接: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≤n,m≤105) 表示节点的数目和询问数目. 接下来一行包含66个有空格分开的整数 a1,b1,a2,b2,a3,b3(1≤a1,a2,a3,b1,b2,b3≤n) 表示新加的三条边为 (a1,b1),(a2,b2),(a3,b3) . 接下来mm行, 每行包含两个整数 si 和 ti (1≤si,ti≤n) , 表示一组询问.
所有数据中mm的和不超过10^6106. 输出描述 对于每组数据, 输出一个整数 S=(∑i=1mi⋅zi) mod (109+7) , 其中z_izi表示第ii组询问的答案. 输入样例 1 10 2 2 4 5 7 8 10 1 5 3 1 输出样例 7
—————————————————————————————————————————— 首先对于给了N个节点求最短路 一定不能直接做了,
发现他加的三条边与查询的边一共就8个点,那么每次对这8个点写folyd不就好了,O(8*8*8)然而写了一发TLE
然后想这样怎么能在优化呢?
想到给定的那6个点是固定的,那么多次求就浪费了
然后考虑,让我查询的就一条边,那么其实也就是6*6条边对这条边松弛,那么复杂度就是O(6*6),
附本题代码 ——————————————————————————————————————————
#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; }