ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年3月23日 558点热度 0人点赞 0条评论

题目传送门: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)));
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: SPFA 最短路 模板 洛谷
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号