1.次小生成树
非严格次小生成树：边权和小于等于最小生成树的边权和
严格次小生成树： 边权和小于最小生成树的边权和
算法：先建好最小生成树，然后对于每条不在最小生成树上的边（u，v，w）如果我们把它放到最小生成树中，会形成一个环，那么再从这个环上删除一个除加进去的边外且小于（或等于）当前w的最大权值边，可以用倍增（或树剖）维护链上的最大值来实现非严格的，对于严格的来说，最大值可能等于w，那么就再维护一个次大值。
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 1e5 + , M = 3e5 + ;
const int INF = 0x3f3f3f3f;
pair<int, pii> e[M];
vector<pii> g[N];
int fa[N], deep[N], anc[N][];
pii mx[N][];
bool vis[M];
void init(int n) {
for (int i = ; i <= n; ++i) fa[i] = i;
}
int Find(int x) {
if(x == fa[x]) return x;
else return fa[x] = Find(fa[x]);
}
pii MX(pii a, pii b) {
pii res = {-INF, -INF};
if(a.fi > b.fi) res.fi = a.fi, res.se = b.fi;
else if(a.fi < b.fi) res.fi = b.fi, res.se = a.fi;
else res.fi = a.fi;
res.se = max(res.se, a.se);
res.se = max(res.se, b.se);
return res;
}
void dfs(int u, int o, int w) {
deep[u] = deep[o] + ;
if(u != ) {
anc[u][] = o;
for (int i = ; i < ; ++i) anc[u][i] = anc[anc[u][i-]][i-];
mx[u][] = {w, -INF};
for (int i = ; i < ; ++i) mx[u][i] = MX(mx[u][i-], mx[anc[u][i-]][i-]);
}
else {
for (int i = ; i < ; ++i) anc[u][i] = o;
for (int i = ; i < ; ++i) mx[o][i] = mx[u][i] = {-INF, -INF};
}
for (pii p : g[u]) {
int v = p.fi;
int w = p.se;
if(v != o) {
dfs(v, u, w);
}
}
}
int lca(int u, int v) {
if(deep[u] < deep[v]) swap(u, v);
for (int i = ; i >= ; --i) if(deep[anc[u][i]] >= deep[v]) u = anc[u][i];
if(u == v) return u;
for (int i = ; i >= ; --i) if(anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i];
return anc[u][];
}
int main() {
int n, m;
LL tot = ;
scanf("%d %d", &n, &m);
for (int i = ; i <= m; ++i) scanf("%d %d %d", &e[i].se.fi, &e[i].se.se, &e[i].fi);
init(n);
sort(e+, e++m);
for (int i = ; i <= m; ++i) {
int x = Find(e[i].se.fi);
int y = Find(e[i].se.se);
if(x == y) vis[i] = true;
else fa[x] = y, g[e[i].se.fi].pb({e[i].se.se, e[i].fi}), g[e[i].se.se].pb({e[i].se.fi, e[i].fi}), tot += e[i].fi;
}
dfs(, , );
LL ans = LONG_MAX;
for (int i = ; i <= m; ++i) {
if(vis[i]) {
int u = e[i].se.fi;
int v = e[i].se.se;
int l = lca(u, v);
pii mm = {-INF, -INF};
for (int i = ; i >= ; i--) if(deep[anc[u][i]] >= deep[l]) mm = MX(mm, mx[u][i]), u = anc[u][i];
;
for (int i = ; i >= ; i--) if(deep[anc[v][i]] >= deep[l]) mm = MX(mm, mx[v][i]), v = anc[v][i] ;
if(mm.fi < e[i].fi) ans = min(ans, e[i].fi + tot - mm.fi);
else if(mm.se < e[i].fi && mm.se != -INF)ans = min(ans, e[i].fi + tot - mm.se);
}
}
printf("%lld\n", ans);
return ;
}
2.次短路
次短路：到某个点的距离比最短路距离大的距离
参照挑战程序设计竞赛P108
到某个点v的次短路要么是其他某个顶点u的最短路再加上u -> v的边，要么是到u的次短路再加上u -> v的边，于是考虑Dijkstra算法更新最短路和次短路。
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head const int N = 5e3 + ;
vector<pii> g[N];
int d[N], dd[N];
priority_queue<pii, vector<pii>, greater<pii> > q;
int main() {
int n, m, u, v, w;
scanf("%d %d", &n, &m);
for (int i = ; i <= m; ++i) {
scanf("%d %d %d", &u, &v, &w);
g[u].pb({v, w});
g[v].pb({u, w});
}
mem(d, 0x7f);
mem(dd, 0x7f);
d[] = ; //dd[1]不能等于0,n=1且自环的情况
q.push({, });
while(!q.empty()) {
pii p = q.top();
q.pop();
int u = p.se;
if(dd[u] < p.fi) continue;
for (int i = ; i < g[u].size(); ++i) {
int v = g[u][i].fi;
int w = g[u][i].se;
int d1 = p.fi + w;
if(d1 < d[v]) {
swap(d1, d[v]);
q.push({d[v], v});
}
if(d1 < dd[v] && d1 > d[v]) {
dd[v] = d1;
q.push({dd[v], v});
}
}
}
printf("%d\n", dd[n]);
return ;
}
ps:最短路记数也可以用Dijkstra,考虑松弛时如果d[v] > d[u] + w, 那么cnt[v] = cnt[u], 如果d[v] == d[u] + w, 那么cnt[v] += cnt[u]。
3.k短路
A* 或者 可持久化堆
都不会，未完待续。。。