[洛谷P2136]拉近距离（负权带环图SPFA）

题目传送门：P2136 拉近距离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

在之前有写过spfa做的题《[NOIP2009]最优贸易（分层图论 + SPFA最长路） – ErikTse Runtime》，不过那道题比较复杂，本题是一道纯模板题。

思路

直接spfa，有几个点需要注意。

• 这里是单向图，根据题意，需要对d[1][N]和d[N][1]取小。
• 注意判环，方法是如果一个点走了N次那么一定存在环。
• 可以用exit(0)来使整个程序结束。
• spfa与dijkstra不同，需要让queue全部更新完才能得到正确的答案，而不是第一次走到终点就作为答案。
• 注意inq数组不要漏了。
• 注意每次spfa需要初始化。
• 注意题目给的w要取相反数作为权值（当然你减去权值也行）。

代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
const int maxn = 1e3 + 10, inf = 1e10;
typedef pair<int, int> PII;
vector<PII> g[maxn];//{点，权值}

int N, M;

int spfa(int s,int t)
{
	int cnt[maxn], d[maxn];
	for(int i = 1;i <= N; ++ i)cnt[i] = 0,d[i] = inf;
	bitset<maxn> inq;
	queue<int> q;
	q.push(s);inq[s] = 1;d[s] = 0;
	while(!q.empty())
	{
		int x = q.front();q.pop();inq[x] = 0;
		cnt[x] ++;
		if(cnt[x] > N)
		{
			printf("Forever love\n");
			exit(0);
		}
		for(auto i : g[x])
		{
			int nx = i.fi, ew = i.se;
			if(d[nx] > d[x] + ew)
			{
				d[nx] = d[x] + ew;
				if(!inq[nx]){q.push(nx);inq[nx] = 1;}
			}
		}
	}
	//全部完成之后d的值才是正确的 
	return d[t];
}

signed main()
{
	 cin >> N >> M;
	 while(M --)
	 {
	 	int x, y, w;scanf("%lld %lld %lld",&x, &y, &w);
	 	g[x].pb({y, -w});
	 }
	 printf("%lld\n",min(spfa(1,N), spfa(N, 1)));
}