C++ 深度优先搜索实现加权有向图最小成本路径 - 限制边数

#include #include #include using namespace std;

const int INF = 2147483647; const int MAXN = 1005; vector<pair<int, int>> g[MAXN]; int n, e, s, t, m, ans = INF; bool vis[MAXN];

void dfs(int u, int cnt, int sum) { if (cnt == m && u == t) { ans = min(ans, sum); return; } if (cnt > m || sum >= ans) return; for (auto& [v, w] : g[u]) { if (!vis[v]) { vis[v] = true; dfs(v, cnt + 1, sum + w); vis[v] = false; } } }

int main() { cin >> n >> e; for (int i = 1; i <= e; i++) { int u, v, w; cin >> u >> v >> w; g[u].push_back({v, w}); } cin >> s >> t >> m; memset(vis, false, sizeof(vis)); vis[s] = true; dfs(s, 0, 0); if (ans == INF) cout << -1 << endl; else cout << ans << endl; return 0; }