题解【洛谷P1807】最长路_NOI导刊2010提高（07）

题面

题解

最长路模板。

只需要在最短路的模板上把符号改一下\(+\)初值赋为\(-1\)即可。

注意一定是单向边，不然出现了正环就没有最长路了，就好比出现了负环就没有最短路了。

只能用\(SPFA\)来写。

(反正总有毒瘤出题人卡

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cctype>

#include <queue>

#define itn int

#define gI gi

using namespace std;

inline int gi()

{

	int f = 1, x = 0; char c = getchar();

	while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar();}

	while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar();}

	return f * x;

}

int n, m, tot, head[200003], nxt[200003], edge[200003], ver[200003];

int dis[200003], vis[200003];

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

{

	ver[++tot] = v, edge[tot] = w, nxt[tot] = head[u], head[u] = tot;

}

inline void SPFA()//真正的SPFA

{

	queue <int> q;

	q.push(1);

	dis[1] = 0;

	vis[1] = 1;

	while (!q.empty())

	{

		int u = q.front(); q.pop();

		vis[u] = 0;

		for (int i = head[u]; i; i = nxt[i])

		{

			int v = ver[i], w = edge[i];

			if (dis[v] < dis[u] + w)//注意符号

			{

				dis[v] = dis[u] + w;

				if (!vis[v]) {q.push(v); vis[v] = 1;}

			}

		}

	}

}

int main()

{

	n = gi(), m = gI();

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

	{

		int u = gi(), v = gI(), w = gi();

		add(u, v, w);//单向边

	}

	memset(dis, -1, sizeof(dis));//赋初值

	SPFA();

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

	return 0;

}