P2136 拉近距离

题面

题目背景

我是源点，你是终点。我们之间有负权环。 ——小明

题目描述

在小明和小红的生活中，有 $N$ 个关键的节点。有 $M$ 个事件，记为一个三元组 $(S_i,T_i,W_i)$，表示从节点 $S_i$ 有一个事件可以转移到 $T_i$，事件的效果就是使他们之间的距离减少 $W_i$。

这些节点构成了一个网络，其中节点 $1$ 和 $N$ 是特殊的，节点 $1$ 代表小明，节点 $N$ 代表小红，其他代表进展的阶段。所有事件可以自由选择是否进行，但每次只能进行当前节点邻接的。请你帮他们写一个程序，计算出他们之间可能的最短距离。

输入格式

第一行，两个正整数 $N,M$。

之后 $M$ 行，每行 $3$ 个空格隔开的整数 $S_i,T_i,W_i$。

输出格式

一行，一个整数表示他们之间可能的最短距离。如果这个距离可以无限缩小，输出Forever love。

样例 #1

样例输入 #1

3 3
1 2 3
2 3 -1
3 1 -10

样例输出 #1

-2

提示

对于 $20\%$ 数据，$N \le 10$，$M \le 50$。

对于 $50\%$ 数据，$N \le 300$，$M \le 5000$。

对于 $100\%$ 数据，$1\le N \le 10^3$，$1\le M \le 10^4$，$|W_i|\le 100$，保证从节点 $1$ 到 $2 \dots N$ 有路径，从节点 $N$ 到 $1 \dots N - 1$ 有路径。

思路

怎么让小明和小红永远在一起呢？

考验阅读理解的时候来了。

大部分人都会和我想的一样，觉得这就是写个最短路顺便判下负环呗。

确实是这样，但是题目中有几个坑人的点。

首先就是事件的效果是使距离减少$W_i$，所以边权要在原来的基础上取负。

其次，小明和小红不一定是谁靠近谁，所以可能是$1\to{n}$或者$n\to{1}$（这才是双向奔赴嘛），于是跑两遍最短路然后取$\min$，如果在这个过程中，发现了有负环，那就可以Forever love了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+7;
const int M=1e4+7;
int n,m,cnt;
struct edge
{
    int to,nxt,d;
}e[M];
int dist[N];
int fir[N];
bool vis[N];
int l[N];
void add(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].nxt=fir[u];
    e[cnt].d=w;
    fir[u]=cnt;
}
void SPFA(int x)
{
    for(int i=1;i<=n;i++)
    {
        l[i]=0;
        dist[i]=INT_MAX;
        vis[i]=false;
    }
    dist[x]=0;
    queue<int> Q;
    Q.push(x);
    while(Q.size())
    {
        int now=Q.front();
        Q.pop();
        vis[now]=false;
        for(int i=fir[now];i;i=e[i].nxt)
        {
            int v=e[i].to;
            int dis=dist[now]+e[i].d;
            if(dis<dist[v])
            {
                l[v]=l[now]+1;
                if(l[v]>=n)
                {
                    printf("Forever love");
                    exit(0);
                }
                dist[v]=dis;
                if(!vis[v])
                {
                    vis[v]=true;
                    Q.push(v);
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,-c);
    }
    SPFA(1);
    int ans=dist[n];
    SPFA(n);
    ans=min(ans,dist[1]);
    printf("%d",ans);
    return 0;
}