[洛谷P2136]拉近距离(负权带环图SPFA)

发布于 2022-03-23  644 次阅读


题目传送门: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)));
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-09