题面
题解
强行将最短路和点分治（长链剖分）融合在一起的题目
构建出字典序最小的最短路树之后，就可以用点分治来解决了
不过有一些细节要注意：
3 3 k
1 2 1
2 3 1
1 3 2
这样建出的最短路树是\(1-2-3\)
而不是\(1-2,1-3\)
相信这组美妙的数据可以帮助你调错
这组\(hack\)数据的核心和上面那个是一样的
代码
#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<algorithm>
#include<queue>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x))
inline int read()
{
int data = 0, w = 1; char ch = getchar();
while(ch != '-' && (!isdigit(ch))) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();
return data * w;
}
const int maxn(30010);
int n, m, K;
struct edge { int next, to, dis; };
inline void add_edge(int, int, int);
namespace Dij
{
std::vector<std::pair<int, int> > g[maxn]; bool vis[maxn];
int dis[maxn];
inline void add_edge(int from, int to, int dis)
{
g[from].push_back(std::make_pair(to, dis));
g[to].push_back(std::make_pair(from, dis));
}
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >,
std::greater<std::pair<int, int> > > Q;
void dfs(int x)
{
vis[x] = 1;
for(std::vector<std::pair<int, int> >::iterator
i = g[x].begin(); i != g[x].end(); ++i)
{
int to = i -> first; if(vis[to]) continue;
if(dis[to] == dis[x] + i -> second)
::add_edge(x, to, i -> second), dfs(to);
}
}
void main()
{
for(RG int i = 1; i <= n; i++) std::sort(g[i].begin(), g[i].end());
for(RG int i = 1; i <= n; i++) dis[i] = INT_MAX >> 1;
Q.push(std::make_pair(dis[1] = 0, 1));
while(!Q.empty())
{
int x = Q.top().second; Q.pop(); if(vis[x]) continue;
vis[x] = 1;
for(std::vector<std::pair<int, int> >::iterator
i = g[x].begin(); i != g[x].end(); ++i)
{
int to = i -> first; if(vis[to]) continue;
if(dis[x] + i -> second < dis[to])
{
dis[to] = dis[x] + i -> second;
Q.push(std::make_pair(dis[to], to));
}
}
}
clear(vis, 0); dfs(1);
}
}
edge e[maxn << 1]; int head[maxn], e_num;
inline void add_edge(int from, int to, int dis)
{
e[++e_num] = (edge) {head[from], to, dis}; head[from] = e_num;
e[++e_num] = (edge) {head[to], from, dis}; head[to] = e_num;
}
bool vis[maxn];
int SIZE, _min, root, size[maxn], stk[maxn], cnt_tdep[maxn];
int top, tdep[maxn], ans, cnt_ans, dep[maxn];
void GetRoot(int x, int fa)
{
size[x] = 1; int tot = 0;
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(vis[to] || to == fa) continue;
GetRoot(to, x); size[x] += size[to];
tot = std::max(tot, size[to]);
}
tot = std::max(tot, SIZE - size[x]);
if(tot < _min) _min = tot, root = x;
}
void GetDep(int x, int fa, int _dep, int _dis)
{
stk[++top] = x;
if(tdep[_dep] <= _dis)
{
if(tdep[_dep] == _dis) ++cnt_tdep[_dep];
else tdep[_dep] = _dis, cnt_tdep[_dep] = 1;
}
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(vis[to] || to == fa) continue;
GetDep(to, x, _dep + 1, _dis + e[i].dis);
}
}
void Calc(int x, int fa, int _dep, int _dis)
{
dep[x] = _dep;
if(dep[x] < K - 1)
{
int nowdis = tdep[K - _dep - 1] + _dis;
if(ans <= nowdis)
{
if(ans == nowdis) cnt_ans += cnt_tdep[K - _dep - 1];
else ans = nowdis, cnt_ans = cnt_tdep[K - _dep - 1];
}
}
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(vis[to] || to == fa) continue;
Calc(to, x, _dep + 1, _dis + e[i].dis);
}
}
void dfs(int x)
{
vis[x] = 1, top = 0;
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(vis[to]) continue;
Calc(to, x, 1, e[i].dis), GetDep(to, x, 1, e[i].dis);
}
if(ans <= tdep[K - 1])
{
if(ans == tdep[K - 1]) cnt_ans += cnt_tdep[K - 1];
else ans = tdep[K - 1], cnt_ans = cnt_tdep[K - 1];
}
for(RG int i = 1; i <= top; i++)
cnt_tdep[dep[stk[i]]] = tdep[dep[stk[i]]] = 0;
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(vis[to]) continue;
SIZE = _min = size[to], root = 0; GetRoot(to, x);
dfs(root);
}
}
int main()
{
n = read(), m = read(), K = read();
for(RG int i = 1, a, b, c; i <= m; i++)
a = read(), b = read(), c = read(),
Dij::add_edge(a, b, c);
Dij::main();
SIZE = _min = n; GetRoot(1, 0); dfs(root);
printf("%d %d\n", ans, cnt_ans);
return 0;
}