第20课 CSP-J大纲知识专题&初赛真题精讲

全面备考2025 CSP-J 初赛 & 复赛直播课

更新中

陈远龙老师主讲 & 答疑

课程题单 - T1005

未购买 · 可先试学32节课

课程目录展开/折叠

视频时长：54:51

视频 PPT&板书讲课代码课后练习

播放快捷键

播放/暂停：空格（或鼠标单击）全屏：F（或鼠标双击）退出全屏：Esc

快进10 / 30 / 60秒：方向键→ / Ctrl + 方向键→ / Shift + 方向键→

快退10 / 30 / 60秒：方向键← / Ctrl + 方向键← / Shift + 方向键←

本节课讲解配套PPT&板书：

本节课讲解到的源代码

源代码下载：第20课 CSP-J大纲知识专题&初赛真题精讲-源代码下载

1. C1144 - 城市交通-1

#include <bits/stdc++.h>
using namespace std;

int n;
int mp[105][105];
int dp[105]; // dp[3] 代表顶点3到顶点n的最短距离 

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= n; j ++)
            cin >> mp[i][j];
    }
    for (int i = 1; i <= n; i ++)
        dp[i] = INT_MAX;
    dp[n] = 0;
    for (int i = n - 1; i >= 1; i --)
    {
        // int res = INT_MAX;
        for (int j = i + 1; j <= n; j ++)
        {
            if (mp[i][j])
            {
                dp[i] = min(dp[i], mp[i][j] + dp[j]);
                // mp[i][j] + dp[j]
                // res = min(res, mp[i][j] + dp[j]);
            }
        }
        // dp[i] = res;
    }

    cout << dp[1];

    return 0;
}

2. C1144 - 城市交通-2

#include <bits/stdc++.h>
using namespace std;

int n;
int mp[105][105];
int dp[105]; // dp[3] 代表顶点3到顶点n的最短距离 

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= n; j ++)
            cin >> mp[i][j];
    }
    for (int i = 1; i <= n; i ++)
        dp[i] = INT_MAX;
    dp[n] = 0;
    for (int i = n - 1; i >= 1; i --)
    {
        for (int j = i + 1; j <= n; j ++)
        {
            if (mp[i][j])
                dp[i] = min(dp[i], mp[i][j] + dp[j]);             
        }
    }
    cout << dp[1];

    return 0;
}

3. C1144 - 城市交通-3

#include <bits/stdc++.h>
using namespace std;

int n;
int mp[105][105];
int dp[105]; // dp[3] 代表顶点3到顶点n的最短距离 

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= n; j ++)
            cin >> mp[i][j];
    }
    fill(dp, dp + n + 1, INT_MAX);
    dp[n] = 0;
    for (int i = n - 1; i >= 1; i --)
    {
        for (int j = i + 1; j <= n; j ++)
        {
            if (mp[i][j])
                dp[i] = min(dp[i], mp[i][j] + dp[j]);             
        }
    }
    cout << dp[1];

    return 0;
}

4. C1144 - 城市交通-4

#include <bits/stdc++.h>
using namespace std;

int n;
int mp[105][105];
int dp[105]; // dp[3] 代表顶点3到顶点n的最短距离 

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= n; j ++)
            cin >> mp[i][j];
    }
    // fill(dp, dp + n + 1, INT_MAX);
    memset(dp, 0x3f, sizeof(dp)); // 0x3f 3f 3f 3f
    dp[n] = 0;
    for (int i = n - 1; i >= 1; i --)
    {
        for (int j = i + 1; j <= n; j ++)
        {
            if (mp[i][j])
                dp[i] = min(dp[i], mp[i][j] + dp[j]);             
        }
    }
    cout << dp[1];

    return 0;
}

5. C1144 - 城市交通-5

#include <bits/stdc++.h>
using namespace std;

int n;
int mp[105][105];
int dp[105]; // dp[3] 代表顶点3到顶点n的最短距离 

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= n; j ++)
            cin >> mp[i][j];
    }
    for (int i = 1; i <= n; i ++)
        dp[i] = INT_MAX;
    // 正推
    dp[1] = 0;
    for (int i = 2; i <= n; i ++)
    {
        for (int j = 1; j < i; j ++)
        {
            if (mp[i][j])
            {
                dp[i] = min(dp[i], mp[i][j] + dp[j]);
            }
        }
    }

    cout << dp[n];

    return 0;
}

本节课无课后练习

本节课答疑

建议大家有问题先通过AI答疑（比如：DeepSeek 等），AI时代需要学会使用AI辅助学习

陈远龙老师视频讲解：如何使用DeepSeek进行答疑？

通过AI未能获得满意解答的，可以联系陈远龙老师答疑