HDU2874这题我Runtime Error(ACCESS_VIOLATION)。贴上我的程序:
#include<iostream>
#include<cstdio>
#include<vector>
#define maxn 100100
using namespace std;
vector<int> a[maxn],b[maxn];
int Mi[maxn][20],o[maxn],ha[maxn],fist[maxn],D[maxn],dep[maxn],F[maxn],lo2[maxn],Min,tot,X,Y,x,y,z,n,m,t,i,S,k,j;
int fin(int x){return (F[x]==x)?x:F[x]=fin(F[x]);}
void dfs(int x,int y,int DEP){
o[++t]=x;fist[x]=t;dep[t]=DEP;
int i;
for (i=0;i<a[x].size();i++)
if (a[x][i]!=y)
D[a[x][i]]=D[x]+b[x][i],dfs(a[x][i],x,DEP+1),o[++t]=x,dep[t]=DEP;
return ;
}
int main(){
while (~scanf("%d %d %d",&n,&m,&k)){
for (i=1;i<=n;i++) F[i]=i;
for (i=1;i<=m;i++){
scanf("%d %d %d",&x,&y,&z);
a[x].push_back(y);b[x].push_back(z);
a[y].push_back(x);b[y].push_back(z);
F[fin(x)]=y;
}
for (i=1;i<=n;i++)
if (fin(i)==i)
dfs(i,0,1);
for (i=2;i<=n;i++) lo2[i]=lo2[i>>1]+1;
for (i=1;i<=n;i++) Mi[i][0]=i;
for (j=1;j<=lo2[n];j++)
for (i=1;i<=n;i++)
X=dep[Mi[i][j-1]],Y=dep[Mi[i+(1<<(j-1))][j-1]],Mi[i][j]=(X<Y)?X:Y;
for (i=1;i<=k;i++){
scanf("%d %d",&x,&y);
if (fin(x)!=fin(y)){printf("Not connected\n");continue;}
S=D[x]+D[y];
x=fist[x];y=fist[y];
if (x>y) swap(x,y);
k=lo2[y-x+1];
X=dep[Mi[x][k]];Y=dep[Mi[y+1-(1<<k)][k]];
Min=(X<Y)?X:Y;
S-=2*D[o[Min]];
printf("%d\n",S);
}
}
return 0;
}