题面
题解
首先把最短路径树建出来（用$Dijkstra$，没试过$SPFA$$\leftarrow$它死了），然后问题就变成了一个关于深度的问题，可以用长链剖分做，所以我们用点分治来做（滑稽）。
有一点要说，这一题数据比较水，如果不用字典序的话，也可以过。如何建立字典序呢？其实我们从$1$号节点开始遍历路径树（不是最短路径树），令一个点的第一关键字是点权，如果点权相等就按照编号大小为第二关键字，维护一个二元组就好了。
点分治时记两个数组$S[i]$和$num[i]$，表示经过$i$个点的路径最大是多少以及在这个情况下有多少条路径。
之前找重心调了好久。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
using std::pair; using std::sort;
using std::priority_queue;
using std::vector; using std::greater;
typedef long long ll;
typedef pair<int, int> pii;
template<typename T>
void read(T &x) {
int flag = 1; x = 0; char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;
}
const int N = 3e4 + 10, Inf = 1 << 30;
int n, m, k, from[N], dist[N], MX, tot;
int cnt, to[N << 1], nxt[N << 1], dis[N << 1];
bool vis[N];
vector<pii> G[N]; priority_queue< pii, vector<pii>, greater<pii> > q;
void addEdge(int u, int v, int w) {
to[++cnt] = v, nxt[cnt] = from[u], dis[cnt] = w, from[u] = cnt;
}
void dijk(int s) {
memset(dist, 0x7777777f, sizeof dist);
dist[s] = 0, q.push((pii){0, s});
while(q.size()) {
int u = q.top().second; q.pop();
if(vis[u]) continue; vis[u] = true;
for(int i = 0; i < G[u].size(); ++i) {
int v = G[u][i].first, w = G[u][i].second + dist[u];
if(dist[v] > w) dist[v] = w, q.push((pii){dist[v], v});
}
}
}
void init(int u) {
vis[u] = 1;
for(int i = 0; i < G[u].size(); ++i) {
int v = G[u][i].first, w = G[u][i].second;
if(vis[v] || w + dist[u] != dist[v]) continue;
addEdge(u, v, w), addEdge(v, u, w), init(v);
}
}
int Size, tmp, p, siz[N], maxnow, S[N], num[N];
inline void upt(int &a, int b) { if(a < b) a = b; }
void getrt(int u, int f) {
int max_part = 0; siz[u] = 1;
for(int i = from[u]; i; i = nxt[i]) {
int v = to[i]; if(vis[v] || v == f) continue;
getrt(v, u); siz[u] += siz[v];
upt(max_part, siz[v]);
} upt(max_part, Size - siz[u]);
if(max_part < tmp) p = u, tmp = max_part;
}
void calc(int u, int f, int now) {
upt(maxnow, now);
if(now == k - 1) {
if(dist[u] == MX) ++tot;
else if(dist[u] > MX) MX = dist[u], tot = 1;
return ;
}
int nowans = -1;
if(S[k - 1 - now] != -1) nowans = dist[u] + S[k - 1 - now];
if(nowans == MX) tot += num[k - 1 - now];
else if(nowans > MX) MX = nowans, tot = num[k - 1 - now];
for(int i = from[u]; i; i = nxt[i]) {
int v = to[i]; if(vis[v] || v == f) continue;
dist[v] = dist[u] + dis[i], calc(v, u, now + 1);
}
}
void update(int u, int f, int now) {
if(now == k - 1) return ;
if(S[now] == dist[u]) ++num[now];
else upt(S[now], dist[u]), num[now] = 1;
for(int i = from[u]; i; i = nxt[i]) {
int v = to[i]; if(vis[v] || v == f) continue;
update(v, u, now + 1);
}
}
void doit(int x) {
p = 0, tmp = Inf, getrt(x, 0), vis[p] = 1, maxnow = 0;
for(int i = from[p]; i; i = nxt[i]) {
int v = to[i]; if(vis[v]) continue;
dist[v] = dis[i], calc(v, p, 1), update(v, p, 1);
}
for(int i = 1; i <= maxnow; ++i) S[i] = -1, num[i] = 0;
for(int i = from[p]; i; i = nxt[i]) {
int v = to[i]; if(vis[v]) continue;
Size = siz[v], doit(v);
}
}
int main () {
read(n), read(m), read(k);
for(int i = 1, u, v, w; i <= m; ++i) {
read(u), read(v), read(w);
G[u].push_back((pii){v, w});
G[v].push_back((pii){u, w});
}
for(int i = 1; i <= n; ++i) sort(G[i].begin(), G[i].end());
dijk(1), memset(vis, 0, sizeof vis), init(1);
Size = n, memset(vis, 0, sizeof vis);
memset(dist, 0, sizeof dist), doit(1);
printf("%d %d\n", MX, tot);
return 0;
}