1

嗨，我想解决此网站http://rosalind.info/problems/cte/上的“通过给定边缘的最短周期”问题。假设我们的特定边（即我们在这个问题中的第一个边）是“E”。我写了一个程序来解决这个问题，我的算法是在'E'的end_node上使用DFS，直到遇到'E'的start_node。它适用于该网站上给出的示例，但是当我使用大数据时，它会进入循环。我尝试了许多简单有向图的示例，但我没有找到为什么它会进入循环。谁能告诉我它是否会循环？

这是我的程序：

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <list>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <stack>


using namespace std;

#define ll long long int
#define pb push_back
#define mk make_pair

const ll maxn = 1e5 + 3;
const ll inf = 1e12 + 10;

vector <ll> cost;

void is_cyclic(int i, bool * recstack,ll cnt,vector <pair<ll,ll>> * vec,ll ind) {
    recstack[i] = true;
    vector <pair<ll, ll>>::iterator it = vec[i].begin();
    for (; it != vec[i].end(); it++) {
        if (it->first == ind) {
            cnt += it->second;
            cost.pb(cnt);
        }
        else {
            if (recstack[it->first] == false) {
                is_cyclic(it->first, recstack, cnt + it->second, vec, ind);
            }
        }
    }
    recstack[i] = false;
}

int main() {
    ll k;
    //file >> k;
    //while (k--) {
        ll n, m;
        cin >> n >> m;
        ll s;
        vector <pair<ll, ll>> * vec;
        vec = new vector<pair<ll, ll>>[n];
        for (int j = 0; j < m; j++) {
            ll a, b, c;
            cin >> a >> b >> c;
            if (j == 0) {
                s = a - 1;
            }
            vec[a - 1].pb(mk(b - 1, c));
        }
        bool * recstack = new bool[n];
        for (int j = 0; j < n; j++) {
            recstack[j] = false;
        }
        ll cnt = 0;
        pair <ll, ll> p;
        p = vec[s][0];
        cnt += p.second;
        recstack[s] = true;
        is_cyclic(p.first, recstack, cnt, vec,s);
        if (cost.size() == 0) {
            cout << -1 << " ";
        }
        else {
            sort(cost.begin(), cost.end());
            cout  << cost[0] << " ";
        }
        cost.clear();
    //}
    return 0;
}
4

1 回答 1

0

首先，您应该使用 BFS，而不是 DFS，来计算未加权图中的最短路径。

其次，几乎不可能弄清楚你的代码是如何工作的。如果您想获得有意义的答案，我建议您清理您的代码。这里有一些提示：

  • 请使用描述变量的作用/含义的变量名称。像这样的变量名std::vector<…&gt; vec会让你的代码很难理解。
  • 添加一些评论来告诉我们你的代码在哪里做什么。
  • 请不要使用 think like #define pb push_back。这使得不是你的每个人都几乎不可能阅读你的代码。
  • 您使用了许多不必要的指针/堆分配（而您没有使用delete它们。）示例是vec或recstack（使std::vector<bool>...）
  • 使用std::numeric_limits而不是定义自己的maxn等。
  • 而不是.push_back(std::make_pair(a,b))，使用.emplace_back(a,b)
于 2018-08-02T12:12:14.550 回答