HDU-2874-森林求LCA/tarjan

http://acm.hdu.edu.cn/showproblem.php?pid=2874

给出一个森林，询问任意两点最短距离。

tarjan跑一遍即可，就是这个题卡内存，vector会MLE，换前向星就好了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<map>

 #include<set>

 #include<stack>

 #include<deque>

 #include<bitset>

 #include<unordered_map>

 #include<unordered_set>

 #include<queue>

 #include<cstdlib>

 #include<ctype.h>

 #include<ctime>

 #include<functional>

 #include<algorithm>

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define pii pair<int,int>

 #define mp make_pair

 #define pb push_back

 #define fi first

 #define se second

 #define inf 0x3f3f3f3f

 #define debug puts("debug")

 #define mid ((L+R)>>1)

 #define lc (id<<1)

 #define rc (id<<1|1)

 const int maxn=;

 const int maxm=;

 const double PI=acos(-1.0);

 const double eps=1e-;

 const LL mod=1e9+;

 LL gcd(LL a,LL b){return b==?a:gcd(b,a%b);}

 LL lcm(LL a,LL b){return a/gcd(a,b)*b;}

 LL qpow(LL a,LL b,LL c){LL r=; for(;b;b>>=,a=a*a%c)if(b&)r=r*a%c;return r;}

 template<class T>

 void prt(T v){for(auto x:v)cout<<x<<' ';cout<<endl;}

 struct Edge{int v,w,next;}e,e1[],e2[];

 int first1[maxn],first2[maxn],tot1,tot2;

 void add1(int u,int v,int w){

     e1[tot1].v=v;

     e1[tot1].w=w;

     e1[tot1].next=first1[u];

     first1[u]=tot1++;

 }

 void add2(int u,int v,int w){

     e2[tot2].v=v;

     e2[tot2].w=w;

     e2[tot2].next=first2[u];

     first2[u]=tot2++;

 }

 bool vis[maxn];

 int f[maxn],d[maxn],ans[];

 int getf(int u){return f[u]==u?u:f[u]=getf(f[u]);}

 void tarjan(int u){

     vis[u]=;

     for(int i=first1[u];~i;i=e1[i].next){

         e=e1[i];

         int v=e.v,w=e.w;

         if(!vis[v]){

             d[v]=d[u]+w;

             tarjan(v);

             f[v]=u;

         }

     }

     for(int i=first2[u];~i;i=e2[i].next){

         e=e2[i];

         int v=e.v,id=e.w;

         if(vis[v]){

             ans[id]=d[u]+d[v]-*d[getf(v)];

         }

     }

 }

 void read(int &n){

     n=; char c=getchar();

     while(c<''||c>'')c=getchar();

     while(c>=''&&c<='') n=(n<<)+(n<<)+c-'',c=getchar();

 }

 int main(){

     int t,n,m,i,j,u,v,w;

     while(~scanf("%d%d%d",&n,&m,&t)){

         for(i=;i<=n;++i)f[i]=i;

         tot1=tot2=;

         memset(first1,-,sizeof(first1));

         memset(first2,-,sizeof(first2));

         while(m--){

             //scanf("%d%d%d",&u,&v,&w);

             read(u),read(v),read(w);

             add1(u,v,w);

             add1(v,u,w);

         }

         for(i=;i<=t;++i){

             ans[i]=-;

             //scanf("%d%d",&u,&v);

             read(u),read(v);

             add2(u,v,i);

             add2(v,u,i);

         }

         memset(d,-,sizeof(d));

         for(i=;i<=n;++i){

             if(d[i]==-) d[i]=,memset(vis,,sizeof(vis)),tarjan(i);

         }

         for(i=;i<=t;++i){

             if(ans[i]==-) puts("Not connected");

             else printf("%d\n",ans[i]);

         }

     }

     return ;

 }