2026-03 · 7级 · 物流网络

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

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

2026-03
数组与向量

正文

// GESP 2026-03 C++ 7级 编程题 2 · 物流网络
// 原题：https://oj.yecheng.tv/p/gs2603l7p2
// 官方原卷：https://gesp.ccf.org.cn/101/attach/1734447340716064.pdf
// 题意：一个物流网络由个城市和条双向公路组成。
// 知识点：数组与向量、字符串、结构体与类、STL
// 参考程序：CCF 原卷官方标程，PDF 抽取后已去行号；本地编译核验通过，供打字练习
// 原卷样例验证：编译失败
// 校订：官方题解框里粘贴了两份完整程序（solve/main 重复定义），保留第一份；算法保持官方原样
//
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Highway {
    int u, v;
    int fee, b;
    bool operator<(const Highway &other) const {
        return b == other.b ? fee < other.fee : b < other.b;
    }
};
void solve() {
    int n, m;
    cin >> n >> m;
    vector<Highway> highways(m);
    for (int i = 0; i < m; i ++)
        cin >> highways[i].u >> highways[i].v >> highways[i].fee >> highways[i].b;
    sort(highways.begin(), highways.end());
    vector<vector<const Highway *> > network(n + 1);
    vector<long long> dp1(n + 1, (long long)1e18);
    vector<long long> dpn(n + 1, (long long)1e18);
    dp1[1] = 0, dpn[n] = 0;
    long long answer = (long long)1e18;
    for (int ri = 0; ri < m; ri ++) {
        const Highway &r = highways[ri];
        answer = min(
            answer,
            min(dp1[r.u] + dpn[r.v],
            dp1[r.v] + dpn[r.u])
            );
        network[r.u].push_back(&r);
        network[r.v].push_back(&r);
        vector<int> cur;
        cur.push_back(r.u), cur.push_back(r.v);
        for (int t = 0; t < cur.size(); t ++) {
            int i = cur[t];
            for (int t2 = 0; t2 < network[i].size(); t2 ++) {
                const Highway* j = network[i][t2];
                int k = (i == j->u ? j->v : j->u);
                if (dp1[i] + j->fee < dp1[k]) {
                    dp1[k] = dp1[i] + j->fee;
                    cur.push_back(k);
                }
            }
        }
        cur.clear();
        cur.push_back(r.u), cur.push_back(r.v);
        for (int t = 0; t < cur.size(); t ++) {
            int i = cur[t];
            for (int t2 = 0; t2 < network[i].size(); t2 ++) {
                const Highway* j = network[i][t2];
                int k = (i == j->u ? j->v : j->u);
                if (dpn[i] + j->fee < dpn[k]) {
                    dpn[k] = dpn[i] + j->fee;
                    cur.push_back(k);
                }
            }
        }
        cur.clear();
    }
    cout << (answer == (long long)1e18 ? -1 : answer) << '\n';
}
int main() {
    solve();
    return 0;
}

2026-03 · 7级 · 物流网络

正文

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