# The Shortest Statement

• 若 s 到 t 的最短路径不经过非树边，直接求出 LCA 就可以轻松得出答案。
• 若 s 到 t 的最短路径经过非树边，就可以直接用非树边的端点作为 s 到 t 的中转点来更新答案。由于非树边最多有 21 条，这样的特殊点最多有 42 个，直接预处理出这 42 个点到其它点的最短路就可以了。

``````#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct Graph
{
struct Vertex
{
vector<int> o, i;
int siz, dep, top, dfn;
};
struct Edge : pair<int, int>
{
ll len;
Edge(int x, int y, ll z) : pair<int, int>(x, y), len(z) {}
};
vector<Vertex> v;
vector<Edge> e;
Graph(int n) : v(n) {}
{
v[ed.first].o.push_back(e.size());
v[ed.second].i.push_back(e.size());
e.push_back(ed);
}
int ch(int u, int i = 0)
{
return e[v[u].o[i]].second;
}
int fa(int u, int i = 0)
{
return e[v[u].i[i]].first;
}
};
struct BellmanFord : Graph
{
BellmanFord(int n) : Graph(n) {}
{
d.assign(v.size(), INF);
vector<int> flag(v.size(), d[s] = 0);
for (deque<int> q(flag[s] = 1, s); !q.empty(); q.pop_front())
for (int u = q.front(), i = flag[u] = 0, k, to; i < v[u].o.size(); ++i)
if (k = v[u].o[i], to = e[k].second,
d[to] > d[u] + e[k].len)
{
d[to] = d[u] + e[k].len;
if (!flag[to])
flag[to] = 1, q.push_back(to);
}
}
};
struct TreeDiagram : BellmanFord
{
TreeDiagram(const Graph &g, int root) : BellmanFord(g.v.size())
{
build(root, g);
int cnt = v[root].dfn = v[root].dep = 1;
dfs(v[root].top = root, cnt);
}
void build(int u, const Graph &g)
{
v[u].siz = 1;
for (int i = 0, k, to; i < g.v[u].o.size(); ++i)
if (k = g.v[u].o[i], to = g.e[k].second, !v[to].siz)
{
build(to, g);
v[u].siz += v[to].siz;
if (v[ch(u)].siz < v[to].siz)
swap(v[u].o.front(), v[u].o.back());
}
}
void dfs(int u, int &cnt)
{
for (int i = 0, to; i < v[u].o.size(); ++i)
{
v[to = ch(u, i)].dfn = ++cnt;
v[to].top = i ? to : v[u].top;
v[to].dep = v[u].dep + 1;
dfs(to, cnt);
}
}
int lca(int x, int y)
{
for (; v[x].top != v[y].top; x = fa(v[x].top))
if (v[v[x].top].dep < v[v[y].top].dep)
swap(x, y);
if (v[x].dep < v[y].dep)
swap(x, y);
return y;
}
};
int main()
{
int n, m;
scanf("%d%d", &n, &m);
BellmanFord g(n + 1);
for (int i = 0, x, y, z; i < m; ++i)
{
scanf("%d%d%d", &x, &y, &z);
}
TreeDiagram t(g, 1);
vector<ll> d[63];
for (int i = m = 0; i < n; ++i)
if (t.v[i].o.size() + t.v[i].i.size() < g.v[i].o.size())