代码详解：完善程序-2

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-09-03 10:57:31
 * 最后修改: 2025-09-03 20:22:36
 * 文件描述: 2024CSP-S  完善程序-2
****************************************************************/
#include <cstdio>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;

const int maxn = 2e5 + 10;
const int maxm = 1e6 + 10;
const int inf  = 522133279; // 0x1f1f1f1f，用于与 memset(..., 0x1f, ...) 保持一致

int n, m, s, t;

/* 邻接链表存图
head[maxn]:存放“每个点的第一条边的编号
nxt[maxm]: 每条边的下一条的编号
to[maxm]: 每条边的终点编号
w[maxm]: 存放“边的权重
tot = 1: 记录当前总共有多少条边，初始化为1
*/
int head[maxn], nxt[maxm], to[maxm], w[maxm], tot = 1;

/*dis[]：距离数组（长度开到 2n）dis[0..n-1]：从起点 s 到每个点的最短路长度。
dis[n..2n-1]（也就是 dis2[v] = dis[n+v]）：从起点 s 到每个点的次短路长度）。*/
int dis[maxn << 1], *dis2;  // dis2 = dis + n


/*pre[]：前驱数组（同样长度 2n，用来回溯路径）
pre[0..n-1]：对应最短路层，pre[v] 存的是“在最短路里到达 v 的前一个结点”的索引（在 0..n-1 这一层里）。
pre[n..2n-1]（也就是 pre2[v] = pre[n+v]）：对应次短路层，pre[n+v] 存“在次短路里到达 v 的前一个结点”的索引。
注意这个索引可能在最短层（< n）或在次短层（≥ n）：*/
int pre[maxn << 1], *pre2;   // pre2 = pre + n

/*  Dijkstra 访问标记，在这份代码里有两层状态（共 2n 个）：0 .. n-1：最短路层,n .. 2n-1：次短路层
因此 vis 的大小也是 2n，按“状态编号 aa”来标记：
vis[aa] == true 表示这个状态（含层信息）已经被堆顶弹出并最终确定了它的距离 dis[aa]，
后续如果队列里还有这个状态的旧条目就直接跳过。*/
bool vis[maxn << 1];       



//建立一条新边 a -> b，权重为 c，编号是 tot。
inline void add(int a, int b, int c) {
    ++tot;             //分配新边编号，从2开始
    nxt[tot] = head[a];//把旧的第一条边挂到 nxt 链表上。
    to[tot]  = b;      // 记录终点
    w[tot]   = c;      // 记录权值
    head[a]  = tot;//更新 a 的第一条边为新建的这条。
}


/**
 * 尝试用 (a -> b, 距离 d) 更新 dis[b]。
 * 若 b < n，则 b 属于“最短层”；若 b >= n，则 b 属于“次短层”。
 * 返回值：是否成功改进 dis[b]。
 *
 * 关键点（① 的位置）：
 *   - 当且仅当准备改进“最短层 b”时（b < n），需要把“旧最短 dis[b] + pre[b]”
 *     推广为“次短层的候选”，即调用 upd(pre[b], n+b, dis[b], q)。
 *   - 这样“旧最短”有机会成为“次短”（更优的次短会覆盖它）。
 */
bool upd(int a, int b, int d, priority_queue<pair<int, int>> &q) {
    if (d >= dis[b]) return false;  // 没有更优，直接拒绝

    if (b < n) {
        // ① 推广“旧最短”为“次短候选”：把旧的 (pre[b] -> b, 距离 = dis[b])
        //    尝试写到“次短层的 b”（即 n + b）
        //    这里利用 upd 自身的判重逻辑，若无改进会直接返回 false
        upd(pre[b], n + b, dis[b], q);
    }

    // ② priority_queue 是大根堆，这里用 (-d, b) 实现“最小距离优先”
    q.push(make_pair(-d, b));

    // 真正写入更优解
    dis[b] = d;
    pre[b] = a;
    return true;
}

/**
 * 双层 Dijkstra：
 *   层 0：最短层（0..n-1）
 *   层 1：次短层（n..2n-1）
 *
 * 队列中的节点索引 aa ∈ [0, 2n)
 *   - a = aa % n 为其对应的原始结点编号
 *   - aa < n 表示当前在最短层；aa >= n 表示当前在次短层
 */
void solve() {

/*pari.first 用于排序的键——放的是“距离的相反数 -d，因为 C++ 默认是大根堆，
把距离取负后，距离越小 -d 越大，就会越早被弹出，相当于实现了最小堆效果。
初始化时也有 q.push(make_pair(0, s));（表示起点距离 0 的相反数仍是 0）。
pair.second：状态编号（节点 + 层）。代码有两层状态：0..n-1 是最短层，n..2n-1 是次短层。这里存的就是这个状态索引*/
    priority_queue<pair<int, int>> q;

    // ③ 用 0x1f 初始化，得到 0x1f1f1f1f，数值正好等于 inf（522133279）
    memset(dis, 0x1f, sizeof(dis));
    //把每个字节置为 0xFF，对 int 就是 -1（补码 0xFFFFFFFF），
    memset(pre, -1,  sizeof(pre));
    memset(vis, 0,   sizeof(vis));

    dis2 = dis + n;   // 指向次短层距离数组
    pre2 = pre + n;   // 指向次短层前驱数组

    // 起点：最短层 s 的距离为 0
    dis[s] = 0;
    q.push(make_pair(0, s)); // (负距离, 结点索引)

    // Dijkstra 主循环
    while (!q.empty()) {
        int aa = q.top().second; q.pop();
        if (vis[aa]) continue;
        vis[aa] = true;

        int a = aa % n; // 对应的原图结点编号

        // 遍历 a 的所有出边
        for (int e = head[a]; e; e = nxt[e]) {
            int b = to[e], c = w[e];

            if (aa < n) {
                // 在“最短层”中松弛边 a -> b
                // 先尝试改进最短层：若失败，再把该条路径作为“次短候选”
                if (!upd(a, b, dis[a] + c, q)) {
                    // ④ 若无法改进最短层，用它去尝试改进“次短层的 b”（n + b）
                    upd(a, n + b, dis[a] + c, q);
                }
            } else {
                // 在“次短层”中只能更新“次短层到次短层”
                upd(n + a, n + b, dis2[a] + c, q);
            }
        }
    }
}

/**
 * 递归输出：从结点 a 回溯直至 s
 *
 * 最终调用形如 out(n + t)，表示要输出“到达 t 的次短路”。
 * 打印时用 a % n + 1 还原为 1..n 的结点编号，直到 a == n + t 换行。
 */
void out(int a) {
    if (a != s) {
        if (a < n) {
            // 在最短层，回溯到 pre[a]
            out(pre[a]);
        } else {
            // 在次短层，回溯到次短层前驱
            // ⑤ 注意：pre2 指向 pre + n，因此 a 对应的原始编号是 a - n
            out(pre2[a - n]);
        }
    }
    printf("%d%c", a % n + 1, " \n"[a == n + t]);
}

int main() {
    // 输入：点数 n，边数 m，起点 s，终点 t（1-based）
    scanf("%d%d%d", &n, &m, &s, &t);
    s--, t--; 
    //因为输入是 1 基（点编号 1…n），而这份代码里所有数组与逻辑都按0 基（0…n-1）来实现的，
    // 所以把 s、t 各减一，是为了把外部的 1 基编号转换成内部的 0 基编号，保持一致。

    // 读入 m 条有向边（a -> b，权重 c）
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a - 1, b - 1, c); //a-1,b-1也是因为起点和终点都是0基
    }

    // 运行双层 Dijkstra
    solve();

    // 若 t 的次短路仍为 inf，表示不存在次短路
    if (dis2[t] == inf) {
        puts("-1");
    } else {
        // 输出次短路长度与路径（从 s 到 t 的第二短）
        printf("%d\n", dis2[t]);
        out(n + t); // 从“次短层的 t”开始回溯输出
    }
    return 0;
}