思路：
LCA裸题。本来是帮pechpo调错，结果自己写了半天…
设$dis_x$是点$x$到根结点距离，不难想到两点$u$、$v$之间最短距离等于$dis_u+dis_v-dis_{LCA(u,v)} imes 2$。
然后我们可以用Tarjan做，然后发现MLE了。
以为是这题卡vector的内存，于是改成了链式前向星，还是MLE。
后来发现题目的内存限制只有32M，算了算，如果将数据离线保存下来，大约有20000K左右，再加上函数里面的栈，似乎确实有点危险。
最后改成用ST做，只用了5852KB。
1 #include<cstdio> 2 #include<cctype> 3 #include<cstring> 4 #include<algorithm> 5 inline int getint() { 6 char ch; 7 while(!isdigit(ch=getchar())); 8 int x=ch^'0'; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 10 return x; 11 } 12 inline int flog2(const float x) { 13 return ((unsigned&)x>>23&255)-127; 14 } 15 const int V=10001,logV=101; 16 struct Edge { 17 int to,w,next; 18 }; 19 Edge edge[V<<1]; 20 int e[V],esz; 21 inline void add_edge(const int u,const int v,const int w) { 22 esz++; 23 edge[esz]=(Edge){v,w,e[u]}; 24 e[u]=esz; 25 } 26 bool vis[V]; 27 int dis[V],dep[V]; 28 int anc[V][logV]; 29 inline void init() { 30 esz=0; 31 memset(vis,0,sizeof vis); 32 memset(dis,0,sizeof dis); 33 memset(anc,0,sizeof anc); 34 memset(dep,0,sizeof dep); 35 memset(e,0,sizeof e); 36 } 37 void dfs(const int x,const int par) { 38 vis[x]=true; 39 anc[x][0]=par; 40 dep[x]=dep[par]+1; 41 for(int i=e[x];i;i=edge[i].next) { 42 int &y=edge[i].to; 43 if(y==par) continue; 44 dis[y]=dis[x]+edge[i].w; 45 dfs(y,x); 46 } 47 } 48 int LCA(int a,int b) { 49 if(dep[a]<dep[b]) std::swap(a,b); 50 for(int i=flog2(dep[a]);i>=0;i--) { 51 if(dep[a]-(1<<i)>=dep[b]) a=anc[a][i]; 52 } 53 if(a==b) return a; 54 for(int i=flog2(dep[a]);i>=0;i--) { 55 if(anc[a][i]!=anc[b][i]) a=anc[a][i],b=anc[b][i]; 56 } 57 return anc[a][0]; 58 } 59 int main() { 60 int n,m,q; 61 while(~scanf("%d%d%d",&n,&m,&q)) { 62 init(); 63 while(m--) { 64 int u=getint(),v=getint(),w=getint(); 65 add_edge(u,v,w); 66 add_edge(v,u,w); 67 } 68 for(int i=1;i<=n;i++) { 69 if(!vis[i]) dfs(i,0); 70 } 71 for(int j=1;j<=flog2(n);j++) { 72 for(int i=1;i<=n;i++) { 73 anc[i][j]=anc[anc[i][j-1]][j-1]; 74 } 75 } 76 while(q--) { 77 int u=getint(),v=getint(); 78 if(int lca=LCA(u,v)) { 79 printf("%d ",dis[u]+dis[v]-dis[lca]*2); 80 } 81 else { 82 puts("Not connected"); 83 } 84 } 85 } 86 return 0; 87 }
本来用Tarjan算法是MLE的，当时是用了三个数组$qx[Q]$,$qy[Q]$,$lca[Q]$，分别存储每一个$x$，$y$和$LCA(x,y)$，Tarjan的时候求出LCA。最后答案输出的时候计算距离。
后来考虑在Tarjan的同时直接将它们之间的距离求出来，这样一下子就节省了两个数组，最后跑了29376K，还是勉强卡过去。
1 #include<cstdio> 2 #include<cctype> 3 #include<cstring> 4 inline int getint() { 5 char ch; 6 while(!isdigit(ch=getchar())); 7 int x=ch^'0'; 8 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 9 return x; 10 } 11 const int V=10001,E=10001,Q=1000001; 12 struct Edge { 13 int to,w,next; 14 }; 15 Edge edge[E<<1]; 16 int e[V],esz; 17 inline void add_edge(int u,int v,int w) { 18 esz++; 19 edge[esz]=(Edge){v,w,e[u]}; 20 e[u]=esz; 21 } 22 struct Query { 23 int to,id,next; 24 }; 25 Query query[Q<<1]; 26 int q[V],qsz; 27 inline void add_query(int u,int v,int id) { 28 qsz++; 29 query[qsz]=(Query){v,id,q[u]}; 30 q[u]=qsz; 31 } 32 class DisjointSet { 33 private: 34 int anc[V]; 35 public: 36 void reset() { 37 for(int i=0;i<V;i++) anc[i]=i; 38 } 39 int Find(int x) { 40 return x==anc[x]?x:anc[x]=Find(anc[x]); 41 } 42 void Union(int x,int y) { 43 anc[Find(x)]=Find(y); 44 } 45 bool isConnected(int x,int y) { 46 return Find(x)==Find(y); 47 } 48 }; 49 DisjointSet s; 50 int ans[Q]; 51 int vis[V]; 52 int dis[V]={0}; 53 int root; 54 void Tarjan(int x,int par) { 55 vis[x]=root; 56 for(int i=e[x];i;i=edge[i].next) { 57 int y=edge[i].to; 58 if(y!=par) { 59 dis[y]=dis[x]+edge[i].w; 60 Tarjan(y,x); 61 s.Union(y,x); 62 } 63 } 64 for(int i=q[x];i;i=query[i].next) { 65 int y=query[i].to; 66 if(vis[y]==root) { 67 ans[query[i].id]=dis[x]+dis[y]-dis[s.Find(y)]*2; 68 } 69 } 70 } 71 inline void init() { 72 s.reset(); 73 esz=qsz=0; 74 for(int i=0;i<Q;i++) ans[i]=-1; 75 memset(vis,0,sizeof vis); 76 memset(e,0,sizeof e); 77 memset(q,0,sizeof q); 78 } 79 int main() { 80 int n,m,q; 81 while(~scanf("%d%d%d",&n,&m,&q)) { 82 init(); 83 while(m--) { 84 int u=getint(),v=getint(),w=getint(); 85 add_edge(u,v,w); 86 add_edge(v,u,w); 87 } 88 for(int i=0;i<q;i++) { 89 int u=getint(),v=getint(); 90 add_query(u,v,i); 91 add_query(v,u,i); 92 } 93 for(int i=1;i<=n;i++) { 94 if(!vis[i]) { 95 root=i; 96 Tarjan(i,0); 97 } 98 } 99 for(int i=0;i<q;i++) { 100 if(~ans[i]) { 101 printf("%d ",ans[i]); 102 } 103 else { 104 puts("Not connected"); 105 } 106 } 107 } 108 return 0; 109 }