【BZOJ 4016】[FJOI2014]最短路径树问题

！ 卡时过了 为什么我的这么慢？姿势不对？？？ -->谢 ws_fqk 我的Do（num[i]）应该用 DO(root) 找了半天的root居然没有用....

define的教训永远忘不了了！！！

优化了好几处才过的...者...

#include 
#include 
#include 
#include 
#define MAXN 30010
using namespace std;
int n,m,k;
bool b[MAXN];
int team[10000000],head,tail,d[MAXN];
int tot,g[MAXN],nnext[MAXN*2],num[MAXN*2],cost[MAXN*2];
int tot0,g0[MAXN],nnext0[MAXN*4],num0[MAXN*4],cost0[MAXN*4];
int tot1,g1[MAXN],nnext1[MAXN*4],num1[MAXN*4],cost1[MAXN*4];
struct H{int x,y,z;}G[MAXN*4];
bool cmp(H a,H b){if(a.x==b.x)return a.y>b.y;return a.xk) return;if(c>T[depth][0]) T[depth][0]=c,T[depth][1]=1;else if(c==T[depth][0]) T[depth][1]++;for(int i=g[x];i;i=nnext[i])if(!b[num[i]]&&num[i]!=fa)Dfs_T(num[i],x,depth+1,c+cost[i]);
}
void Do(int x)
{for(int i=0;i<=k;i++) N[i][0]=N[i][1]=0;N[0][1]=1;b[x]=true;for(int i=g[x];i;i=nnext[i])if(!b[num[i]]){for(int i=0;i<=k;i++) T[i][0]=T[i][1]=0;Dfs_T(num[i],-1,1,cost[i]);for(int i=1;i<=k;i++){if(ans0>n>>m>>k; k--;for(int i=1;i<=m;i++){int x,y,z;scanf("%d %d %d",&x,&y,&z);G[i]=(H){x,y,z};G[i+m]=(H){y,x,z};tot0++;nnext0[tot0]=g0[x],g0[x]=tot0,num0[tot0]=y;cost0[tot0]=z;tot0++;nnext0[tot0]=g0[y],g0[y]=tot0,num0[tot0]=x,cost0[tot0]=z;}SPFA(); sort(G+1,G+m*2+1,cmp);for(int i=1;i<=m*2;i++){int x=G[i].x,y=G[i].y,z=G[i].z;if(d[x]+z==d[y])tot1++,nnext1[tot1]=g1[x],g1[x]=tot1,num1[tot1]=y,cost1[tot1]=z;}memset(b,false,sizeof(b));Dfs_Road(1);memset(b,false,sizeof(b));root=0,sum=n,max_son[0]=n+1;Get_Root(1,-1);Do(root);cout<