发现NOIP大纲里有这个，所以写一写
次小生成树
分为严格次小生成树和非严格次小生成树，前者要求此生成树的权值和严格大于最小生成树，后者是非严格大于；
对于这个问题，我们首先求出原图的最小生成树，然后发现次小生成树是最小生成树只删一条边，然后加一条边得到的，于是我们可以枚举要加的这条边，然后分以下情况：
- 要求严格次小生成树；
这时我们要找到要加的这条边的左右两个端点在树上的路径中的权值最大的边，如果这两个值不相等，则去掉这个边，如果相等，则查找要加的这条边的左右两个端点在树上的路径中的权值严格次大的边，然后去掉（如果没有就不加这条边）；
- 要求非严格次小生成树；
直接找要加的这条边的左右两个端点在树上的路径中的权值最大的边然后去掉即可；
可以发现，前者的操作比较麻烦，需要维护最大值和严格次大值；
对于这两个操作，我们可以用树剖 + 线段树来解决，下面例题的代码便是如此解决的，时间复杂度 $ \Theta(m \log^2n) $，不难发现，此时间复杂度非常正确，只不过作者常数太大过不了最后的大点；
例题：Luogu P4180 [BJWC2010] 严格次小生成树
求的是严格次小生成树；
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
#define FI(n) FastIO::read(n)
#define FO(n) FastIO::write(n)
#define Flush FastIO::Fflush()
namespace FastIO {
const int SIZE = 1 << 16;
char buf[SIZE], obuf[SIZE], str[60];
int bi = SIZE, bn = SIZE, opt;
inline int read(register char *s) {
while(bn) {
for (; bi < bn && buf[bi] <= ' '; bi = -~bi);
if (bi < bn) break;
bn = fread(buf, 1, SIZE, stdin);
bi &= 0;
}
register int sn=0;
while(bn) {
for (; bi < bn && buf[bi] > ' '; bi = -~bi) s[sn++] = buf[bi];
if(bi < bn) break;
bn = fread(buf,1,SIZE,stdin);
bi &= 0;
}
s[sn] &= 0;
return sn;
}
inline bool read(register int &x){
int n = read(str), bf = 0;
if(!n) return 0;
register int i=0;
(str[i] == '-') && (bf = 1, i = -~i);
(str[i] == '+') && (i = -~i);
for (x = 0; i < n; i = -~i) x = (x << 3) + (x << 1) + (str[i] ^ 48);
bf && (x = ~x + 1);
return 1;
}
// inline bool read(register long long &x) {
// int n = read(str), bf = 1;
// if(!n) return 0;
// register int i=0;
// (str[i] == '-') && (bf = -1,i = -~i);
// for (x = 0; i < n; i= -~i) x = (x << 3) + (x << 1) + (str[i] ^ 48);
// (bf < 0) && (x = ~x + 1);
// return 1;
// }
inline void write(register int x) {
if(!x) obuf[opt++] = '0';
else {
(x < 0) && (obuf[opt++] = '-', x = ~x + 1);
register int sn = 0;
while(x) str[sn++] = x % 10 + '0', x /= 10;
for (register int i = sn - 1; i >= 0; i = ~-i) obuf[opt++] = str[i];
}
(opt >= (SIZE >> 1)) && (fwrite(obuf, 1, opt, stdout), opt &= 0);
}
// inline void write(register long long x) {
// if(!x) obuf[opt++] = '0';
// else {
// (x < 0) && (obuf[opt++] = '-', x = ~x + 1);
// register int sn = 0;
// while(x) str[sn++] = x % 10 + '0', x /= 10;
// for (register int i = sn - 1; i >= 0; i = ~-i) obuf[opt++] = str[i];
// }
// (opt >= (SIZE >> 1)) && (fwrite(obuf, 1, opt, stdout), opt &= 0);
// }
inline void write(register unsigned long long x){
if(!x) obuf[opt++] = '0';
else {
register int sn=0;
while(x) str[sn++] = x % 10 + '0', x /= 10;
for (register int i = sn - 1 ; i >= 0 ; i = ~-i)obuf[opt++] = str[i];
}
(opt >= (SIZE >> 1)) && (fwrite(obuf, 1, opt, stdout), opt &= 0);
}
inline void write(register char x) {
obuf[opt++] = x;
(opt >= (SIZE >> 1)) && (fwrite(obuf, 1, opt, stdout), opt &= 0);
}
inline void Fflush(){
opt && fwrite(obuf, 1, opt, stdout);
opt &= 0;
}
}
struct sss{
int f, t;
long long w;
bool operator <(const sss &A) const {
return w < A.w;
}
}ed[5000005];
struct sas{
int t, ne;
long long w;
}e[2000005];
int h[2000005], cnt;
inline void add(int u, int v, long long ww) {
e[++cnt].t = v;
e[cnt].ne = h[u];
h[u] = cnt;
e[cnt].w = ww;
}
int f[5000005];
int find(int x) {
if (x != f[x]) f[x] = find(f[x]);
return f[x];
}
bool vis[5000005];
long long su;
inline void Kru() {
sort(ed + 1, ed + 1 + m);
for (int i = 1; i <= n; i++) f[i] = i;
int sum = 0;
for (int i = 1; i <= m; i++) {
if (sum == n - 1) break;
int x = find(ed[i].f);
int y = find(ed[i].t);
if (x != y) {
f[x] = y;
sum++;
vis[i] = true;
add(ed[i].f, ed[i].t, ed[i].w);
add(ed[i].t, ed[i].f, ed[i].w);
su += ed[i].w;
}
}
}
long long a[1000005];
int fa[1000005], siz[1000005], hson[1000005], htop[1000005], dep[1000005], dfn[1000005], nfd[1000005], dcnt;
long long aa, bb;
namespace SEG{
inline int ls(int x) {
return x << 1;
}
inline int rs(int x) {
return x << 1 | 1;
}
struct sss{
int l, r;
long long ma, cma;
}tr[2000005];
inline void push_up(int id) {
if (tr[ls(id)].ma != tr[rs(id)].ma) {
tr[id].ma = max(tr[ls(id)].ma, tr[rs(id)].ma);
tr[id].cma = min(tr[ls(id)].ma, tr[rs(id)].ma);
} else {
tr[id].ma = tr[ls(id)].ma;
tr[id].cma = max(tr[ls(id)].cma, tr[rs(id)].cma);
}
}
void bt(int id, int l, int r) {
tr[id].l = l;
tr[id].r = r;
if (l == r) {
tr[id].ma = a[nfd[l]];
tr[id].cma = -1;
return;
}
int mid = (l + r) >> 1;
bt(ls(id), l, mid);
bt(rs(id), mid + 1, r);
push_up(id);
}
void ask(int id, int l, int r) {
if (tr[id].l >= l && tr[id].r <= r) {
if (aa <= tr[id].ma) {
aa = tr[id].ma;
bb = max(bb, tr[id].cma);
} else {
bb = max(bb, tr[id].ma);
}
return;
}
int mid = (tr[id].l + tr[id].r) >> 1;
if (l <= mid) ask(ls(id), l, r);
if (r > mid) ask(rs(id), l, r);
}
}
namespace TCS{
void dfs1(int x, int ff) {
fa[x] = ff;
dep[x] = dep[ff] + 1;
hson[x] = -1;
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (u == ff) continue;
dfs1(u, x);
siz[x] += siz[u];
if (hson[x] == -1 || siz[hson[x]] < siz[u]) hson[x] = u;
}
}
void dfs(int x) {
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (u == fa[x]) continue;
a[u] = e[i].w;
dfs(u);
}
}
void dfs2(int x, int t) {
htop[x] = t;
dfn[x] = ++dcnt;
nfd[dcnt] = x;
if (hson[x] == -1) return;
dfs2(hson[x], t);
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (u == fa[x] || u == hson[x]) continue;
dfs2(u, u);
}
}
inline pair<long long, long long> ask(int x, int y) {
aa = -1;
bb = -1;
while(htop[x] != htop[y]) {
if (dep[htop[x]] < dep[htop[y]]) swap(x, y);
SEG::ask(1, dfn[htop[x]], dfn[x]);
x = fa[htop[x]];
}
if (x == y) return {aa, bb};
if (dfn[x] > dfn[y]) swap(x, y);
SEG::ask(1, dfn[x] + 1, dfn[y]);
return {aa, bb};
}
}
long long ans;
signed main() {
FI(n);
FI(m);
for (int i = 1; i <= m; i++) {
FI(ed[i].f);
FI(ed[i].t);
FI(ed[i].w);
}
Kru();
TCS::dfs1(1, 0);
TCS::dfs(1);
TCS::dfs2(1, 1);
SEG::bt(1, 1, dcnt);
ans = LONG_LONG_MAX;
for (int i = 1; i <= m; i++) {
if (vis[i] || (ed[i].f == ed[i].t)) continue;
pair<long long, long long> p = TCS::ask(ed[i].f, ed[i].t);
if (p.first != ed[i].w) {
ans = min(ans, su - p.first + ed[i].w);
} else if (p.second != -1) {
ans = min(ans, su - p.second + ed[i].w);
}
}
FO(ans);
Flush;
return 0;
}
突然发现貌似可以倍增做，看来常数大是有原因的。。。（不过这种方法应该也能过啊）；
单源次短路
分为两种，一种是可以重复经过一条边，一种是不可以；
也分为严格，不严格；
对于后者，首先建出最短路DAG（其实就是存一下pre），然后暴力删边暴力跑m边最短路即可；
时间复杂度： $ \Theta(m(n + m) \log m) $；
由于思路过于粗暴，在此不放代码（正经人谁考这个啊）；
对于前者，在dij的时候记一下最短路和次短路，每次若最短路成功更新，则将次短路赋值成以前的次短路，否则判断以下当前的待更新值是否在这两个之间，若是则更新（具体见代码）；
时间复杂度： $ \Theta((n + m) \log m) $
求严格可重次短路；
点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int n, r;
struct sss{
int t, ne, w;
}e[500005];
int h[500005], cnt;
void add(int u, int v, int ww) {
e[++cnt].t = v;
e[cnt].ne = h[u];
h[u] = cnt;
e[cnt].w = ww;
}
int dis[5005][2]; //0最短路，1次短路；
void dij(int x) {
memset(dis, 0x3f, sizeof(dis));
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
q.push({0, x});
dis[x][0] = 0;
while(!q.empty()) {
int t = q.top().second;
int di = q.top().first;
q.pop();
for (int i = h[t]; i; i = e[i].ne) {
int u = e[i].t;
if (dis[u][0] > di + e[i].w) {
dis[u][1] = dis[u][0];
dis[u][0] = di + e[i].w;
q.push({dis[u][1], u});
q.push({dis[u][0], u});
} else if (dis[u][0] < di + e[i].w && dis[u][1] > di + e[i].w) { //若求非严格大于，则前面的 < 改为 <= ；
dis[u][1] = di + e[i].w; //若在中间，则更新；
q.push({dis[u][1], u});
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> r;
int x, y, w;
for (int i = 1; i <= r; i++) {
cin >> x >> y >> w;
add(x, y, w);
add(y, x, w);
}
dij(1);
cout << dis[n][1];
return 0;
}