无话可说，拿LCA的离线写法写的，开始在note2里多存了个int，调了一晚上的内存超限，后来不存了，直接写了个ans存距离，就过了，很难受
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn=10000+10; const int maxm=1000000+10; int n,m,c,k1,k2; int cc[maxn]; int hade1[maxn],hade2[maxn]; int ans[maxm]; int vis[maxn]; int d[maxn]; struct note1 { int to; int next; int len; }aa[maxn*2]; struct note2 { int id; int to; int next; }bb[maxm*2]; void addage1(int fr,int to,int len) { aa[k1].to=to; aa[k1].len=len; aa[k1].next=hade1[fr]; hade1[fr]=k1++; } void addage2(int fr,int to,int id) { bb[k2].to=to; bb[k2].next=hade2[fr]; bb[k2].id=id; hade2[fr]=k2++; } int found(int x) { if(x==cc[x]) return x; else return cc[x]=found(cc[x]); } void unit(int x,int y) { x=found(x); y=found(y); if(x==y) return; cc[y]=x; } void tarjan(int u,int val,int k) { vis[u]=k; d[u]=val; for(int i=hade1[u];i!=-1;i=aa[i].next) { int v=aa[i].to; if(!vis[v]) { tarjan(v,d[u]+aa[i].len,k); unit(u,v); } } for(int i=hade2[u];i!=-1;i=bb[i].next) { int v=bb[i].to; if(vis[v]==k) { int id=bb[i].id; ans[id]=d[u]+d[v]-2*d[found(v)]; } } } void init() { memset(hade1,-1,sizeof(hade1)); memset(hade2,-1,sizeof(hade2)); memset(ans,-1,sizeof(ans)); memset(aa,0,sizeof(aa)); memset(bb,0,sizeof(bb)); memset(d,0,sizeof(d)); memset(vis,0,sizeof(vis)); for(int i=0;i<=n;i++) cc[i]=i; k1=0; k2=0; } int main() { while(~scanf("%d%d%d",&n,&m,&c)) { init(); int fr,to,len; for(int i=1;i<=m;i++) { scanf("%d%d%d",&fr,&to,&len); addage1(fr,to,len); addage1(to,fr,len); } for(int i=0;i<c;i++) { scanf("%d%d",&fr,&to); addage2(fr,to,i); addage2(to,fr,i); } for(int i=1;i<=n;i++) if(!vis[i]) tarjan(i,0,i); for(int i=0;i<c;i++) { if(ans[i]==-1) printf("Not connected\n"); else printf("%d\n",ans[i]); } } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/7545328.html
