Teleporter（传送门，使用至少0，1，。。。N次传送门的最短路） · znzryb
## 思路讲解
注意，不能直接跑分层图，会TLE。
那怎么办呢？可以用传送门，先确定一些种子节点，再跑多源最短路。
一个比较重要的剪枝其实在这里。
```cpp
FOR(j, 1, N) {
Dis[i][j] = Dis[i - 1][j];
}
priority_queue < DIS > pq;
FOR(u, 1, N) {
for (auto &v : jie[u]) {
Dis[i][u] = min(Dis[i - 1][v], Dis[i][u]);
}
}
FOR(u, 1, N) {
// 超了，或者和原来一样，就不要了
if (Dis[i][u] != Dis[i - 1][u]) {
pq.push({Dis[i][u], u});
}
}
```
## AC代码
914ms，在dij中算跑的很快的。
[https://qoj.ac/submission/1310755](https://qoj.ac/submission/1310755)
::: 源代码
```cpp
// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef _DEBUG
template<typename T> void _print(T x) {
cerr << x;
}
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) {
cerr << "[ ";
for (T i : v) _print(i), cerr << " ";
cerr << "]";
}
template<typename T> void _print(set<T> s) {
cerr << "{ ";
for (T i : s) _print(i), cerr << " ";
cerr << "}";
}
template<typename T, typename U> void _print(pair<T, U> p) {
cerr << "{";
_print(p.first);
cerr << ", ";
_print(p.second);
cerr << "}";
}
template<typename T, typename U> void _print(map<T, U> m) {
cerr << "{ ";
for (auto &p : m) _print(p), cerr << " ";
cerr << "}";
}
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T >> v) {
cerr << "{\n"; for (auto i : v) _print(i), cerr << "\n"; cerr << " }";
}
#endif
using ll = long long; using ull = unsigned long long;
using ld = double; using LD = long double;
using i128 = __int128;
using pdd = pair<ld, ld>; using plb = pair<ll, bool>;
using pll = pair<ll, ll>; using vll = vector<ll>; using vb = vector<bool>;
using tll = tuple<ll, ll, ll>; using vii = vector<int>;
using vpll = vector<pll>; using vtll = vector<tll>;
using vdb = vector<ld>; using vc = vector<char>;
using arr3 = array<ll, 3> ; using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)5e3+10, INF = (ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9+7; // 998244353;
static constexpr double eps = 1e-8; const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;
inline void __();
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// cin>>lT;
// while(lT--)
__();
return 0;
}
/*
*/
vector<arr2> g[MAXN];
vector<ll> jie[MAXN];
bool vis[MAXN][MAXN];
ll Dis[MAXN][MAXN];
ll ans[MAXN];
void dfs(int u, int fa) {
for (auto &[v, w] : g[u]) {
if (v == fa) continue;
Dis[0][v] = Dis[0][u] + w;
ans[0] += Dis[0][v];
dfs(v, u);
}
}
struct DIS{
ll dis, u;
bool operator<(const DIS & o) const{
return dis > o.dis;
}
};
arr2 edge[2 * MAXN];
inline void __() {
cin >> N >> M;
FOR(i, 1, N - 1) {
ll u, v, w;
cin >> u >> v >> w;
g[u].PB({v, w});
g[v].PB({u, w});
}
FOR(i, 0, N + 5) {
FOR(j, 0, N + 5) {
Dis[i][j] = INF;
}
}
vector < ll > li;
FOR(i, 1, M) {
// cin >> edge[i][0] >> edge[i][1];
ll u, v;
cin >> u >> v;
jie[u].PB(v);
jie[v].PB(u);
}
Dis[0][1] = 0;
dfs(1, 1);
FOR(i, 1, N) {
FOR(j, 1, N) {
Dis[i][j] = Dis[i - 1][j];
}
priority_queue < DIS > pq;
FOR(u, 1, N) {
for (auto &v : jie[u]) {
Dis[i][u] = min(Dis[i - 1][v], Dis[i][u]);
}
}
FOR(u, 1, N) {
if (Dis[i][u] != Dis[i - 1][u]) {
pq.push({Dis[i][u], u});
}
}
//#ifdef LOCAL
// debug(pq.empty());
//#endif
while (!pq.empty()) {
auto[dis, u] = pq.top();
pq.pop();
if (vis[i][u]) continue;
vis[i][u] = true;
Dis[i][u] = dis;
for (auto &[v, w] : g[u]) {
if (vis[i][v]) continue;
if (dis + w >= Dis[i][v]) continue;
pq.push({dis + w, v});
Dis[i][v] = dis + w;
}
}
FOR(j, 1, N) {
ans[i] += Dis[i][j];
}
if (ans[i] == ans[i - 1]) {
FOR(j, i + 1, N) {
ans[j] = ans[i];
}
break;
}
}
FOR(lim, 0, N) {
cout << ans[lim] << "\n";
}
}
/*
TLE
https://vjudge.net/solution/63520490
赛时可以 A 过去
AC 914 ms
https://qoj.ac/submission/1310755
*/
```
:::
## 心路历程（WA，TLE，MLE……）