题目链接
题解
对于建树
dij建出最短路图
在最短路图上dfs，先走字典序最小的可达点
得到最短路树
然后就是经典的点分治了
维护每个深度的最远距离合并就好了
代码
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxn = 30007;
#define mp std::make_pair
#define pr std::pair<int,int>
std::vector<int>v[maxn];
#define INF 0x3f3f3f3f
int hh[maxn] , tt[maxn << 2] , ww[maxn << 2] , nn[maxn << 2] , cc = 1 , vv[maxn] , Dis[maxn] , uu[maxn];
int n , k , head[maxn] , to[maxn << 1] , w[maxn << 1] , next[maxn << 1] , cnt;
int vis[maxn] , root , sum , son[maxn] , F[maxn] ,f[maxn],g[maxn] ,Depdis[maxn] ,sg[maxn],md,deep[maxn] , dis[maxn] , ans , num;
void Add(int x , int y , int z) { tt[++cc] = y,ww[cc] = z,nn[cc] = hh[x],hh[x] = cc; }
void add_edge(int x , int y , int z) { to[++cnt] = y,w[cnt] = z,next[cnt] = head[x],head[x] = cnt; }
std::priority_queue<pr> q;
void dijkstra() {
memset(Dis,0x3f,sizeof(Dis));
Dis[1] = 0 , q.push(mp(0 , 1));
while(!q.empty()) {
int x = q.top().second;q.pop();
if(vv[x]) continue;
vv[x] = 1;
for(int i = hh[x];i;i = nn[i])
if(Dis[x] == Dis[tt[i]] + ww[i])
v[tt[i]].push_back(i ^ 1);
for(int i = hh[x] ; i ; i = nn[i])
if(Dis[tt[i]] > Dis[x] + ww[i])
Dis[tt[i]] = Dis[x] + ww[i] , q.push(mp(-Dis[tt[i]] , tt[i]));
}
}
inline bool cmp(int a ,int b) { return tt[a] < tt[b]; }
void dfs(int x) {
std::sort(v[x].begin(),v[x].end(),cmp);
for(int i = 0;i < v[x].size();i ++ )
if(!uu[tt[v[x][i]]]) {
uu[tt[v[x][i]]] = 1;
add_edge(x,tt[v[x][i]],ww[v[x][i]]);
add_edge(tt[v[x][i]],x,ww[v[x][i]]);
dfs(tt[v[x][i]]);
}
}
void getroot(int x,int fa) {
F[x] = 0,son[x] = 1;
for(int i = head[x] ;i;i = next[i])
if(!vis[to[i]] && to[i] != fa)
getroot(to[i],x),son[x] += son[to[i]],F[x] = std::max(F[x],son[to[i]]);
F[x] = std::max(F[x] , sum - son[x]);
if(F[x] < F[root]) root = x;
}
void getdeep(int x,int fa) {
for(int i = head[x] ; i ; i = next[i]) {
if(!vis[to[i]] && to[i] != fa) {
deep[to[i]] = deep[x] + 1,dis[to[i]] = dis[x] + w[i],md = std::max(md,deep[to[i]]);
if(dis[to[i]] > f[deep[to[i]]]) f[deep[to[i]]] = dis[to[i]],Depdis[deep[to[i]]] = 1;
else if(dis[to[i]] == f[deep[to[i]]]) Depdis[deep[to[i]]] ++ ;
getdeep(to[i],x);
}
}
}
void solve(int x,int sm = 0) {
vis[x] = 1;
for(int i = head[x] ; i ; i = next[i]) {
if(!vis[to[i]]) {
md = deep[to[i]] = 1,dis[to[i]] = w[i],f[1] = w[i],Depdis[1] = 1,getdeep(to[i],x);
for(int j = 1;j <= md && j <= k;j ++ ) {
if(ans < f[j] + g[k - j]) ans = f[j] + g[k - j],num = Depdis[j] * sg[k - j];
else if(ans == f[j] + g[k - j])num += Depdis[j] * sg[k - j];
}
for(int j = 1;j <= md && j <= k;j ++ ) {
if(g[j] < f[j]) g[j] = f[j] , sg[j] = Depdis[j];
else if(g[j] == f[j]) sg[j] += Depdis[j];
}
for(int j = 1;j <= md;j ++ ) f[j] = -INF , Depdis[j] = 0;
sm = std::max(sm,md);
}
}
for(int i = 1;i <= sm && i <= k;i ++ ) g[i] = -INF , sg[i] = 0;
for(int i = head[x];i;i = next[i])
if(!vis[to[i]]) {
root = 0;
sm = son[to[i]];
getroot(to[i] , x);
solve(root);
}
}
int main() {
int m;
scanf("%d%d%d",&n,&m,&k);
k -- ;
for(int x,y,z,i = 1;i <= m ;i ++) scanf("%d%d%d",&x,&y,&z),Add(x,y,z),Add(y,x,z);
dijkstra(),uu[1] = 1,dfs(1);
memset(f,0xc0,sizeof(f)) ; memset(g,0xc0,sizeof(g)),g[0] = 0,sg[0] = 1;
F[0] = INF,sum = n;
getroot(1,0);
solve(root);
printf("%d %d
", ans,num);
return 0;
}