Probelm Terrorists
题目大意
给一张n个点，m条边的无向图。共有q个询问，每次询问u到v的最短路。
n <= 100000 , n-1 <= m <= n + 50 , q <= 50000。
解题分析
注意到m的范围比较特殊，所以可以看成是一棵树加上若干条非树边。
将所有的非树边所连接的点取出来，每个关键点跑一次单源最短路。
对于一次询问u，v，其可能的答案路径为直接从树上跑，或者经过一个关键点中转。
参考程序
1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 #include <queue> 5 #include <cstring> 6 using namespace std; 7 #define INF 2000000000 8 #define V 100008 9 #define E 300008 10 #define clr(x,v) memset(x,v,sizeof(x)) 11 int cnt,n,m,q; 12 int ui[100],vi[100],wi[100],f[100100],l[100100][20],dep[100100],s[100100]; 13 int id[V],rk[108],num,dist[108][V]; 14 struct edge{ 15 int u,w; 16 }; 17 vector <edge> e[100100]; 18 struct line{ 19 int u,v,w,nt; 20 }eg[E]; 21 int lt[V],sum; 22 void add(int u,int v,int w){ 23 eg[++sum]=(line){u,v,w,lt[u]}; 24 lt[u]=sum; 25 } 26 int father(int x) 27 { 28 if(f[x]==x)return x; 29 f[x]=father(f[x]); 30 return f[x]; 31 } 32 33 void dfs(int x,int fa,int sum) 34 { 35 l[x][0]=fa; 36 s[x]=sum; 37 dep[x]=dep[fa]+1; 38 for(int i = 0;i < e[x].size();i++) 39 { 40 int u=e[x][i].u; 41 if(u!=fa) 42 { 43 dfs(u,x,sum+e[x][i].w); 44 } 45 } 46 } 47 48 int lca(int a,int b) 49 { 50 if(dep[a]<dep[b])swap(a,b); 51 int d=dep[a]-dep[b]; 52 for(int i = 0;i <= 18;i++) 53 if(d&(1<<i))a=l[a][i]; 54 if(a==b)return a; 55 for(int i = 18;i >= 0;i--) 56 if(l[a][i]!=l[b][i]) 57 { 58 a=l[a][i]; 59 b=l[b][i]; 60 } 61 return l[a][0]; 62 } 63 int dis(int x,int y){ 64 int p=lca(x,y); 65 return s[x]+s[y]-s[p]*2; 66 } 67 68 int d[V],pd[V]; 69 queue <int> Q; 70 void spfa(int s){ 71 for (int i=1;i<=n;i++){ 72 d[i]=INF; 73 pd[i]=0; 74 } 75 d[s]=0; pd[s]=1; Q.push(s); 76 while (!Q.empty()){ 77 int u=Q.front(); 78 Q.pop(); 79 for (int i=lt[u];i;i=eg[i].nt){ 80 int v=eg[i].v; 81 if (d[u]+eg[i].w<d[v]){ 82 d[v]=d[u]+eg[i].w; 83 if (!pd[v]){ 84 pd[v]=1; 85 Q.push(v); 86 } 87 } 88 } 89 pd[u]=0; 90 } 91 for (int i=1;i<=n;i++) dist[id[s]][i]=d[i]; 92 } 93 void work() 94 { 95 for(int i = 1;i <= 18;i++) 96 for(int j = 1;j <= n;j++) 97 l[j][i]=l[l[j][i-1]][i-1]; 98 for (int i=1;i<=num;i++) spfa(rk[i]); 99 while (q--){ 100 int u,v; 101 scanf("%d%d",&u,&v); 102 int ans=dis(u,v); 103 for (int i=1;i<=num;i++) 104 ans=min(ans,dist[i][u]+dist[i][v]); 105 printf("%d ",ans); 106 } 107 } 108 int main() 109 { 110 int t,cas=0; 111 scanf("%d",&t); 112 while(t--) 113 { 114 clr(lt,0); sum=0; 115 cnt=0; num=0; 116 clr(id,0); 117 printf("Case %d: ",++cas); 118 scanf("%d%d%d",&n,&m,&q); 119 for(int i = 1;i <= n;i++)e[i].clear(); 120 for(int i = 1;i <= n;i++)f[i]=i; 121 for(int i = 1;i <= m;i++) 122 { 123 int u,v,w; 124 scanf("%d%d%d",&u,&v,&w); 125 add(u,v,w); 126 add(v,u,w); 127 if(father(u)!=father(v)) 128 { 129 f[father(u)]=father(v); 130 e[u].push_back((edge){v,w}); 131 e[v].push_back((edge){u,w}); 132 } 133 else 134 { 135 cnt++; 136 ui[cnt]=u; 137 vi[cnt]=v; 138 wi[cnt]=w; 139 if (!id[u]){ 140 id[u]=++num; 141 rk[num]=u; 142 } 143 if (!id[v]){ 144 id[v]=++num; 145 rk[num]=v; 146 } 147 } 148 } 149 dfs(1,0,0); 150 work(); 151 } 152 return 0; 153 }