C++(clang++11) 解法, 执行用时: 113ms, 内存消耗: 6472K, 提交时间: 2020-11-13 13:52:21

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define pir pair<int,int>
using namespace std;
const int N=1e5+10;
vector<pir>G[N];
int n,m,mv,cnt,root,siz,K;
int s[N],froot,f[2][N],g[2][N];
bool vis[N];
int to[N<<1],nxt[N<<1],head[N],W[N<<1],totE;
#define add(a,b,c) (to[++totE]=b,nxt[totE]=head[a],W[totE]=c,head[a]=totE)
int d[N];

void dijkstra()
{
	priority_queue<pir,vector<pir>,greater<pir> >q;
	memset(d,127,sizeof d);
	q.push(make_pair(d[1]=0,1));
	int p,dis,w,v;
	while(!q.empty())
	{
		pir h=q.top();
		q.pop();
		dis=h.first;
		p=h.second;
		if(d[p]^dis)
		continue;
		sort(G[p].begin(),G[p].end());
		for(int i=0;i<G[p].size();i++)
		{
			if(d[v=G[p][i].first]>dis+(w=G[p][i].second))
			{
				q.push(make_pair(d[v]=dis+w,v));
			}
		}
	}
}
void Build(int u)
{
	int v;
	vis[u]=1;
	for(int i=0;i<G[u].size();i++)
	{
		if(!vis[v=G[u][i].first]&&d[v]==d[u]+G[u][i].second)
		{
			add(v,u,G[u][i].second);
			add(u,v,G[u][i].second);
			Build(v);
		}
	}
}
void getroot(int u,int fa)
{
	s[u]=1;
	int mx=0,v;
	for(int it=head[u];it;it=nxt[it])
	{
		if(!vis[v=to[it]]&&(v^fa))
		{
			getroot(v,u);
			s[u]+=s[v];
			if(s[v]>mx)
			mx=s[v];
		}
	}
	if(siz-mx>mx)
	mx=siz-mx;
	if(froot>mx)
	root=u,froot=mx;
}
void dfs(int u,int fa,int dep)
{
	if(dep>K)
	return;
	int v;
	if(d[u]>g[0][dep])
	g[0][dep]=d[u],g[1][dep]=0;
	if(d[u]>=g[0][dep])
	g[1][dep]++;
	for(int i=head[u];i;i=nxt[i])
	{
		if(!vis[v=to[i]]&&(v^fa))
		{
			d[v]=d[u]+W[i];
			dfs(v,u,dep+1);
		}
	}
}
void solve(int u,int S)
{
	vis[u]=1;
	f[0][0]=0;
	f[1][0]=1;
	int v;
	for(int i=head[u];i;i=nxt[i])
	{
		if(!vis[v=to[i]])
		{
			d[v]=W[i];
			dfs(v,u,1);
			for(int j=1;j<=K;j++)
			{
				if(g[0][j]+f[0][K-j]>mv)
				mv=g[0][j]+f[0][K-j],cnt=0;
				if(g[0][j]+f[0][K-j]>=mv)
				cnt+=g[1][j]*f[1][K-j]; 
			}
			for(int j=1;j<=K;j++)
			{
				if(g[0][j]>f[0][j])
				f[0][j]=g[0][j],f[1][j]=0;
				if(g[0][j]>=f[0][j])
				f[1][j]+=g[1][j];
				g[0][j]=g[1][j]=0;
			}
		}
	}
	for(int i=0;i<=K;i++)
	f[0][i]=f[1][i]=0;
	for(int i=head[u];i;i=nxt[i])
	{
		if(!vis[v=to[i]])
		{
			froot=siz=s[v];
			root=0;
			getroot(v,u);
			solve(root,s[v]);
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&K);
	--K;
	for(int a,b,c,i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		G[a].push_back(make_pair(b,c));
		G[b].push_back(make_pair(a,c));
	}
	dijkstra();
	Build(1);
	memset(vis,0,sizeof vis);
	froot=siz=n;
	getroot(1,root=0);
	solve(root,n);
	printf("%d %d\n",mv,cnt);
	return 0;
}