c++实现
时间: 2023-09-18 07:13:55 浏览: 46
以下是该问题的C++代码实现,与Python3代码实现类似,使用了拓扑排序和动态规划的方法:
```c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 110;
int n, m;
vector<pair<int, int>> graph[N];
int in_degree[N];
int distance[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a, b, x;
cin >> a >> b >> x;
graph[a].push_back({b, x});
in_degree[b]++;
}
queue<int> q;
for (int i = 1; i <= n; i++)
{
if (in_degree[i] == 0)
{
q.push(i);
}
}
while (!q.empty())
{
int u = q.front();
q.pop();
for (auto [v, w] : graph[u])
{
in_degree[v]--;
distance[v] = max(distance[v], distance[u] + w);
if (in_degree[v] == 0)
{
q.push(v);
}
}
}
cout << distance[n] << endl;
return 0;
}
```
注意代码中 auto [v, w] : graph[u] 的写法是 C++17 中的结构化绑定,可以用来方便地遍历 vector 中的 pair。如果编译器不支持此特性,可以将其写成 for (auto it : graph[u]) { auto v = it.first, w = it.second; } 的形式。