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;i<n;i++){
    for(int j=1;j<=m;j++){
        d[v[j]]=min(d[v[j]],d[u[j]]+w[j]);
    }
}
for(int j=1;j<=m;j++){
    if(d[v[j]]>d[u[j]]+w[j]){
        cout<<"Forever love"<<endl;
        return 0;
    }
}

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

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

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

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

AC 记录

AC记录