最长路

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <vector>

using namespace std;

//Mystery_Sky

//

#define maxn 1000010

#define maxm 5000050

#define INF 0x3f3f3f3f

queue <int> q;

int ind[maxn], dis[maxn];

struct Edge{

	int to, next, w;

}edge[maxn];

int head[maxn], cnt, ans;

int n, m;

inline void add_edge(int u, int v, int w)

{

	edge[++cnt].to = v;

	edge[cnt].w = w;

	edge[cnt].next = head[u];

	head[u] = cnt;

}

inline void topo()

{

	for(int i = 1; i <= n; i++) {

		if(!ind[i]) {

			q.push(i);

		}

	}

	dis[1] = INF;

	while(!q.empty()) {

		int u = q.front();

		q.pop();

		for(int i = head[u]; i ; i = edge[i].next) {

			int v = edge[i].to;

//			printf("%d %d %d\n", u, v, edge[i].w);

			ind[v]--;

			dis[v] = max(dis[v], dis[u] + edge[i].w);

			if(!ind[v]) q.push(v);

		}

	}

}

int u, v, w;

int main() {

	scanf("%d%d", &n, &m);

	for(int i = 1; i <= m; i++) {

		scanf("%d%d%d", &u, &v, &w);

		add_edge(u, v, w);

		ind[v]++;

	}

	topo();

	if(dis[n]) printf("%d\n", dis[n]-INF);

	else printf("-1\n");

	return 0;

}
巴特西

洛谷 P1807 最长路_NOI导刊2010提高（07）

最长路

最新文章

热门文章
