P2136 拉近距离 题解

题目传送门

可能更好的阅读体验

题目大意

对于一个有向图 \(G\)：有 \(N\) 个点，\(M\) 个边，把每一条边用三元组 \((S_i,T_i,W_i)\)，其中 \(S_i,t_i\) 表示两个端点，\(W_i\) 表示这条边的长度。

如果这个图中从点 \(1\) 到点 \(N\) 的最短路可以无限缩小，请输出 Forever love，否则输出最短路长度。

思路分析

通过数据范围我们发现这题的最短路要处理负权。

我们又可以发现这里的最短路不一样的地方在于，以前的最短路走一条边加上边的长度，这里的最短路走一条边减去一条边的长度。所以在做最短路之前，我们要把所有的 \(W_i\) 都变成它的相反数（即乘上一个 \(-1\)）。

题目中要求输出Forever love的情况是最短路可以无限缩小，那显然，只有在图中有负权环的时候最短路才能无限缩小，所以我们的最短路算法还要能找负权环。

能处理负权，还能找负权环并求出最短路的算法只有 Bellman-Ford 符合我们的要求。这里可以不用 SPFA 进行优化，因为 \(O(MN)\) 的算法可以跑过该题的数据范围。

代码剖析

建边与 Bellman-Ford 的初始化

for(int i=1;i<=m;i++){
	int x,y,z;
	cin>>x>>y>>z;
	u[i]=x;
	v[i]=y;
	w[i]=-z;
}
for(int i=1;i<=n;i++){
	d[i]=INT_MAX;
}

Bellman-Ford 算法的建边不使用邻接表，而是使用三个数组存储起点，终点与边的权值。

注意在开始的时候要将最短路数组初始化成 INT_MAX（因此存储最短路的数组要开long long）。

求最短路

d[1]=0;
for(int i=1;id[u[j]]+w[j]){
		cout<<"Forever love"<

Bellman-Ford 算法求最短路基于松弛操作。对所有边进行 \(n-1\) 次松弛操作（即尝试经过某个点有没有可能使得路径更短）就能求出单源最短路。

为了避免出现负权环，我们再进行一次检查，如果在求完最短路的情况下还有边可以松弛，那就说明这个图中不存在最短路（即存在负权环），直接输出Forever love。

因为小明和小红都有可能拉近距离，所以我们要再跑一次 \(N\) 到 \(1\) 的最短路。

如果跑完两次最短路确定图内不含有负权环，那么直接输出 \(1\) 到 \(N\) 的最短路与 \(N\) 到 \(1\) 的最短路的较小值。

AC 记录

AC记录

洛谷题解

相关

标签