对拍结果是不一致

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

Dijkstra 和暴力枚举都写好了，在那个有负权边的图上各求一次 0 到 3 的距离。补全暴力枚举里的 go，输出三样：Dijkstra 的答案 / 暴力的答案 / 两者是否相同（相同输出结果一致，否则结果不一致）。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 写一个暴力枚举当标尺 Bellman-Ford 的做法 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

typedef long long ll;
const ll INF = 1000000000;                       // 走不到的点记这个值，输出时写成 -1
using Graph = vector<vector<pair<int, int>>>;    // g[u] 里放 (邻居 v, 边权 w)

// 七个点的无向图（和 Python 版同一组数据）：0-1:2 0-2:1 1-3:3 2-4:9 3-4:1 5-6:7
const vector<vector<int>> E7 = {{0, 1, 2}, {0, 2, 1}, {1, 3, 3}, {2, 4, 9}, {3, 4, 1}, {5, 6, 7}};
// 主连通块五个点、五条边（求最小生成树用）
const vector<vector<int>> E5 = {{0, 1, 2}, {0, 2, 1}, {1, 3, 3}, {2, 4, 9}, {3, 4, 1}};
// 有向负权反例：0→1:4 0→2:5 2→1:-3 1→3:1
const Graph NEG = {{{1, 4}, {2, 5}}, {{3, 1}}, {{1, -3}}, {}};
// 同一张图，只把 2→1 那条边改成 +3
const Graph POS = {{{1, 4}, {2, 5}}, {{3, 1}}, {{1, 3}}, {}};
// 有负环：0→1:1 1→2:-1 2→1:-1
const Graph CYC = {{{1, 1}}, {{2, -1}}, {{1, -1}}};

vector<ll> dijkstra(const Graph& g, int s) {
    vector<ll> d(g.size(), INF);
    vector<bool> done(g.size(), false);
    // 小根堆：greater 让距离小的先出（不写就是大根堆）
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    d[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [du, u] = pq.top();
        pq.pop();
        if (done[u]) continue;
        done[u] = true;
        for (auto [v, w] : g[u]) {
            if (du + w < d[v]) {
                d[v] = du + w;
                pq.push({d[v], v});
            }
        }
    }
    return d;
}

ll best_path;

void go(const Graph& g, int u, int t, ll c, vector<bool>& seen) {
    // TODO: 到了 t 就用 c 更新 best_path 并返回
    // TODO: 否则对每个还没走过的邻居：标记、走下去、回来后撤销标记
    (void)g; (void)u; (void)t; (void)c; (void)seen;
}

ll brute(const Graph& g, int s, int t) {
    // 把 s 到 t 所有不重复经过点的路径都走一遍，取最短
    best_path = INF;
    vector<bool> seen(g.size(), false);
    seen[s] = true;
    go(g, s, t, 0, seen);
    return best_path;
}

string verdict(ll a, ll b) {
    return a == b ? "结果一致" : "结果不一致";
}

int main() {
    ll a = dijkstra(NEG, 0)[3], b = brute(NEG, 0, 3);
    cout << a << "/" << b << "/" << verdict(a, b) << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

对拍结果是不一致

更多题目

全部评论