2023-12 · 7级 · 商品交易

GESP 标程 · 考级真题 · 代码 · cpp · 难度 5/5 · 共 1334 字

CCF 原卷官方标程 · 数组与向量、字符串、STL、位运算 · 本地编译通过（抽取破损已校订）

2023-12
数组与向量

正文

// GESP 2023-12 C++ 7级 编程题 1 · 商品交易
// 原题：https://oj.yecheng.tv/p/gs2312l7p1
// 官方原卷：https://gesp.ccf.org.cn/101/attach/1584918444376096.pdf
// 题意：市场上共有种商品，编号从至 ，其中，第种商品价值元。
// 知识点：数组与向量、字符串、STL、位运算
// 参考程序：CCF 原卷官方标程，PDF 抽取后已去行号；本地编译核验通过，供打字练习
// 原卷样例验证：编译失败
// 校订：数组名 queue 与 std::queue 冲突，重命名为 que（算法不变）；算法保持官方原样
//
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int max_n = 1e5 + 10;
int n;
vector<int> edge[max_n];
int val[max_n];
int min_dist[max_n];
int que[max_n], qh, qt;
void bfs(int src) {
    qh = qt = 0;
    memset(min_dist, 127, sizeof(min_dist));
    que[++qt] = src;
    min_dist[src] = 0;
    while (qh < qt) {
        int u = que[++qh];
        for (auto v: edge[u]) {
            if (min_dist[u] + 1 < min_dist[v]) {
                min_dist[v] = min_dist[u] + 1;
                que[++qt] = v;
            }
        }
    }
}
int main() {
    int m, src, dst;
    ios::sync_with_stdio(false);
    cin >> n >> m >> src >> dst;
    for (int i = 0; i < n; ++i) {
        cin >> val[i];
    }
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        edge[x].push_back(y);
    }
    bfs(src);
    if (min_dist[dst] > n) {
        cout << "No solution\n";
    }
    else {
        cout << min_dist[dst] - val[src] + val[dst] << '\n';
    }
    return 0;
}

2023-12 · 7级 · 商品交易

正文

GESP 标程 · 考级真题的其它内容