HDU-2874-森林求LCA/tarjan

http://acm.hdu.edu.cn/showproblem.php?pid=2874
给出一个森林，询问任意两点最短距离。
tarjan跑一遍即可，就是这个题卡内存，vector会MLE，换前向星就好了。
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<map>
  5 #include<set>
  6 #include<stack>
  7 #include<deque>
  8 #include<bitset>
  9 #include<unordered_map>
 10 #include<unordered_set>
 11 #include<queue>
 12 #include<cstdlib>
 13 #include<ctype.h>
 14 #include<ctime>
 15 #include<functional>
 16 #include<algorithm>
 17 #include<bits/stdc++.h>
 18 using namespace std;
 19 #define LL long long 
 20 #define pii pair<int,int>
 21 #define mp make_pair
 22 #define pb push_back
 23 #define fi first
 24 #define se second
 25 #define inf 0x3f3f3f3f
 26 #define debug puts("debug")
 27 #define mid ((L+R)>>1)
 28 #define lc (id<<1)
 29 #define rc (id<<1|1)
 30 const int maxn=10010;
 31 const int maxm=50050;
 32 const double PI=acos(-1.0);
 33 const double eps=1e-6;
 34 const LL mod=1e9+7;
 35 LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
 36 LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
 37 LL qpow(LL a,LL b,LL c){LL r=1; for(;b;b>>=1,a=a*a%c)if(b&1)r=r*a%c;return r;}
 38 template<class T>
 39 void prt(T v){for(auto x:v)cout<<x<<' ';cout<<endl;}
 40 struct Edge{int v,w,next;}e,e1[20020],e2[2000020];
 41 int first1[maxn],first2[maxn],tot1,tot2;
 42 void add1(int u,int v,int w){
 43     e1[tot1].v=v;
 44     e1[tot1].w=w;
 45     e1[tot1].next=first1[u];
 46     first1[u]=tot1++;
 47 }
 48 void add2(int u,int v,int w){
 49     e2[tot2].v=v;
 50     e2[tot2].w=w;
 51     e2[tot2].next=first2[u];
 52     first2[u]=tot2++;
 53 }
 54 
 55 bool vis[maxn];
 56 int f[maxn],d[maxn],ans[1000010];
 57 int getf(int u){return f[u]==u?u:f[u]=getf(f[u]);}
 58 void tarjan(int u){
 59     vis[u]=1;
 60     for(int i=first1[u];~i;i=e1[i].next){
 61         e=e1[i];
 62         int v=e.v,w=e.w;
 63         if(!vis[v]){
 64             d[v]=d[u]+w;
 65             tarjan(v);
 66             f[v]=u;
 67         }
 68     }
 69     for(int i=first2[u];~i;i=e2[i].next){
 70         e=e2[i];
 71         int v=e.v,id=e.w;
 72         if(vis[v]){
 73             ans[id]=d[u]+d[v]-2*d[getf(v)];
 74         }
 75     }
 76 }
 77 void read(int &n){
 78     n=0; char c=getchar();
 79     while(c<'0'||c>'9')c=getchar();
 80     while(c>='0'&&c<='9') n=(n<<3)+(n<<1)+c-'0',c=getchar();    
 81 }
 82 int main(){
 83     int t,n,m,i,j,u,v,w;
 84     while(~scanf("%d%d%d",&n,&m,&t)){
 85         for(i=1;i<=n;++i)f[i]=i;
 86         tot1=tot2=0;
 87         memset(first1,-1,sizeof(first1));
 88         memset(first2,-1,sizeof(first2));
 89         while(m--){
 90             //scanf("%d%d%d",&u,&v,&w);
 91             read(u),read(v),read(w);
 92             add1(u,v,w);
 93             add1(v,u,w);
 94         }
 95         for(i=1;i<=t;++i){
 96             ans[i]=-1;
 97             //scanf("%d%d",&u,&v);
 98             read(u),read(v);
 99             add2(u,v,i);
100             add2(v,u,i);
101         }
102         memset(d,-1,sizeof(d));
103         for(i=1;i<=n;++i){
104             if(d[i]==-1) d[i]=0,memset(vis,0,sizeof(vis)),tarjan(i);
105         }
106         for(i=1;i<=t;++i){
107             if(ans[i]==-1) puts("Not connected");
108             else printf("%d
",ans[i]);
109         }
110     }
111     return 0;
112 }