（次短路） 已知一个有 $n$ 个点 $m$ 条边的有向图 $G$，并且给定图中的两个点 $s$ 和 $t$，求次短路（长度严格大于最短路的最短路径）。如果不存在，输出一行 $-1$。如果存在，输出两行，第一行表示次短路的长度，第二行表示次短路的一个方案。

1#include <cstdio>2#include <queue>3#include <utility>4#include <cstring>5using namespace std;6 7const int maxn = 2e5+10, maxm = 1e6+10, inf = 522133279;8 9int n, m, s, t;10int head[maxn], nxt[maxm], to[maxm], w[maxm], tot = 1;11int dis[maxn<<1], *dis2;12int pre[maxn<<1], *pre2;13bool vis[maxn<<1];14 15void add(int a, int b, int c) {16    ++tot;17    nxt[tot] = head[a];18    to[tot] = b;19    w[tot] = c;20    head[a] = tot;21}22 23bool upd(int a, int b, int d, priority_queue<pair<int, int>> &q) {24    if (d >= dis[b]) return false;25    if (b < n) ___①___;26    q.push(___②___);27    dis[b] = d;28    pre[b] = a;29    return true;30}31 32void solve() {33    priority_queue<pair<int, int>> q;34    q.push(make_pair(0, s));35    memset(dis, ___③___, sizeof(dis));36    memset(pre, -1, sizeof(pre));37    dis2 = dis+n;38    pre2 = pre+n;39    dis[s] = 0;40    while (!q.empty()) {41        int aa = q.top().second; q.pop();42        if (vis[aa]) continue;43        vis[aa] = true;44        int a = aa % n;45        for (int e = head[a]; e; e = nxt[e]) {46            int b = to[e], c = w[e];47            if (aa < n) {48                if (!upd(a, b, dis[a]+c, q))49                    ___④__;50            } else51                upd(n+a, n+b, dis2[a]+c, q);52        }53    }54}55 56void out(int a) {57    if (a != s) {58        if (a < n) out(pre[a]);59        else out(___⑤___);60    }61    printf("%d%c", a%n+1, " \n"[a == n+t]);62}63 64int main() {65    scanf("%d%d%d%d", &n, &m, &s, &t);66    s--, t--;67    for (int i = 0; i < m; ++i) {68        int a, b, c;69        scanf("%d%d%d", &a, &b, &c);70        add(a-1, b-1, c);71    }72    solve();73    if (dis2[t] == inf) puts("-1");74    else {75        printf("%d\n", dis2[t]);76        out(n+t);77    }78}