Shortest-path tree

幸好有大佬帮我,不然就死翘翘了hhh

#include <bits/stdc++.h>
using namespace std;
const int N=3e4+50;
int dis[N],vis[N],n,m,k;

struct node{
    int to,val;
    bool operator <(const node &res)const{
        return to<res.to;
    };
};

struct vv{
    int to,val;
};

struct Q{
    int to,val;
    bool operator <(const Q &res)const{
        return val>res.val;
    };
};
vector<node>V[N];
vector<vv>G[N];
void dij()//以1为根跑dij.
{
    memset(vis,0,sizeof vis);
    memset(dis,0x3f,sizeof dis);
    priority_queue<Q>q;dis[1]=0;
    q.push({1,0});
    while(q.size())
    {
        Q t=q.top();
        q.pop();
        if(vis[t.to])    continue;
        vis[t.to]=1;
        for(int i=0;i<(int)V[t.to].size();i++)
        {
            int v=V[t.to][i].to;int co=V[t.to][i].val;
            if(dis[t.to]+co<dis[v])
            {
                dis[v]=dis[t.to]+co;
                q.push({v,dis[v]});
            }
        }
    }
    memset(vis,0,sizeof vis);
}

void dfs(int u,int fa,int ds)//把图建好.
{
    for(int i=0;i<(int)V[u].size();i++)
    {
        int t=V[u][i].to,co=V[u][i].val;
        if(co+ds>dis[t]||vis[t]||t==fa)    continue;
        vis[t]=1;
        G[u].push_back({t,co});
        G[t].push_back({u,co});
        dfs(t,u,ds+co);
    }
}

int root=0,dp[N],siz[N],ans1,ans2,sum,Vis[N],id,num[N];
//dis i存某层的最大值.
vector<int>D[N];//记录下每个子树每层搜到的距离.
void f_dis(int u,int pre,int dep,int coin)//算下是不是要更新答案
{
    D[dep].push_back(coin);
    if(dep>k)   return;
    if(coin+dis[k-dep]>ans1)
    {
        ans1=coin+dis[k-dep];
        ans2=num[k-dep];
    }
    else if(coin+dis[k-dep]==ans1)
    {
        ans2+=num[k-dep];
    }
    for(int i=0;i<(int)G[u].size();i++)
    {
        int v=G[u][i].to;
        if(!Vis[v]&&v!=pre)    f_dis(v,u,dep+1,coin+G[u][i].val);
    }
}

void f_root(int u,int pre)
{
    dp[u]=0;siz[u]=1;
    for(int i=0;i<(int)G[u].size();i++)
    {
        int v=G[u][i].to;
        if(v==pre||Vis[v])  continue;
        f_root(v,u);siz[u]+=siz[v];
        dp[u]=max(dp[u],siz[v]);
    }dp[u]=max(dp[u],sum-siz[u]);
    if(dp[u]<dp[root])  root=u;
}
int size[N],maxv[N];
int nowsize;
void dfssize(int u,int f)
{
    nowsize++;
    size[u]=1;
    maxv[u]=0;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i].to;
        if(v==f||Vis[v])    continue;
        dfssize(v,u);
        size[u]+=size[v];
        if(size[v]>maxv[u])maxv[u]=size[v];
    }
}

void solve(int u)//分治这个点统计答案.
{
    memset(num,0,sizeof num);
    memset(dis,0,sizeof dis);
    num[0]=1;
    nowsize=0;
    dfssize(u,u);
    if(nowsize<=k+1)return;
    for(int i=0;i<=k+1;i++) D[i].clear();
    Vis[u]=1;
    for(int i=0;i<(int)G[u].size();i++)
    {
        int v=G[u][i].to;
        if(Vis[v])  continue;
        f_dis(v,u,1,G[u][i].val);
        for(int j=0;j<=k;j++)
        {
            for(int h=0;h<(int)D[j].size();h++)
            {
                int temp=D[j][h];
                if(temp==dis[j])
                {
                    num[j]++;
                }
                else if(temp>dis[j])
                {
                    dis[j]=temp;
                    num[j]=1;
                }
            }
            D[j].clear();
        }
    }
    for(int i=0;i<(int)G[u].size();i++)
    {
        int v=G[u][i].to;
        sum=siz[v];
        dp[0]=n;root=0;
        if(Vis[v])  continue;
        f_root(v,root);
        solve(root);
    }
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        ans1=0,ans2=0;
        scanf("%d%d%d",&n,&m,&k);k--;
        for(int i=1;i<=n;i++)    V[i].clear();
        for(int i=1;i<=n;i++)    G[i].clear();
        memset(Vis,0,sizeof Vis);
        memset(vis,0,sizeof vis);
        for(int i=1;i<=m;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            V[u].push_back({v,w});
            V[v].push_back({u,w});
        }
        for(int i=1;i<=n;i++)    sort(V[i].begin(),V[i].end());
        dij();dis[0]=0;
        dfs(1,0,0);
        //以上皆为建图...
        dp[0]=sum=n;
        f_root(1,0);
        solve(root);
        printf("%d %d\n",ans1,ans2);
        //点分治
    }
    return 0;
}