SCP 模拟 · SCP 2021 第一轮（初赛）模拟 第 17 题

#include <cstdio>
 
const int N = 5010;
const int M = 20010;
const int inf = 1073741823;

int e, bg[N], nx[M], to[M], wt[M];
inline void link(int u, int v, int w) {
    to[++e] = v;
    nx[e] = bg[u];
    wt[e] = w;
    bg[u] = e;
}

int n, m, u, v, w;
int f[N], h[N << 1];

void update(int x, int y) {
    x += n - 1;
    for (h[x] = y; x; x >>= 1)
        h[x >> 1] = f[h[x]] < f[h[x^1]] ? h[x] : h[x^1];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i != m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        link(u, v, w);
    }
    int nn = n << 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j != nn; ++j)
            h[j] = 0;
        for (int j = 0; j <= n; ++j)
            f[j] = inf;
        f[i] = 0;
        update(i, i);
        for (int j = i; true; j = h[1]) {
            if (f[j] == inf) break;
            for (int k = bg[j]; k; k = nx[k]) {

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

本题考查程序阅读与C++基础语法，需要模拟程序执行过程，跟踪变量值的变化。

常见误区：忽略变量的初始值，循环次数计算错误，运算符优先级搞错，数据类型转换不留意。

核心概念：程序执行的基本单位是语句，按顺序执行。变量在内存中存储值，赋值操作改变变量的值。

推导分析：逐行模拟，用表格记录每个变量的值变化；注意++i（先加后用）和i++（先用后加）的区别；整数除法会截断小数部分。

避坑指南：循环终止条件影响执行次数；未初始化的变量值不确定。

解题技巧：遇到程序阅读题时，在草稿纸上建立变量跟踪表，逐行记录变量变化。