求助,哪里错了qwq
  • 板块P1807 最长路
  • 楼主Stevehim
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/1/2 16:24
  • 上次更新2023/10/24 05:48:43
查看原帖
求助,哪里错了qwq
759274
Stevehim楼主2023/1/2 16:24

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;
}

2023/1/2 16:24
加载中...