RT,刚学拓扑,找题解模仿了一下,然后怎么调都过不去
#include <bits/stdc++.h>
//P1807
#define maxn 600000
using namespace std;
struct edge {
int from;
int to;
int cost;
};
vector<edge> p[maxn];
queue<int> q; //存储结点
int in[maxn];
int out[maxn];
edge x;
int u, v, w;
int ma[maxn] = {0};
int bj[maxn] = {0}; //标记数组
int n, m;
int topsort() {
int tot = 0; //这个题解可能直接抄的板子,这个是用来计数的
for (int i = 1; i <= n; i++) {
if (in[i] == 0) {
q.push(i); //先推入
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0, sz = p[u].size(); i < sz; i++) { //减少占用
in[p[u][i].to]--;
if (bj[u] == 1) { //被标记了
if (ma[p[u][i].to] < ma[u] + p[u][i].cost) {
ma[p[u][i].to] = ma[u] + p[u][i].cost; //计算边权和,是入度为0的结点的最大值加上这个点链接我的结点之间边的边权
bj[p[u][i].to] = 1; //打上标记,标记数组是用来 看这个点能不能从1到达
}
if (in[p[u][i].to] == 0) {
q.push(p[u][i].to);
}
}
}
}
return tot; //所以说是板子
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> x.from >> x.to >> x.cost;
in[x.to] ++;
p[x.from].push_back(x); //推入
}
ma[n] = -1;
bj[1] = 1;
topsort();
cout << ma[n];
return 0;
}