题目背景

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

题目描述

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

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

输入输出格式

输入格式:

\(1\)行,两个正整数\(N,M\).

之后\(M\)行,每行\(3\)个空格隔开的整数\(S_i,T_i,W_i\)

输出格式:

一行,一个整数表示他们之间可能的最短距离。如果这个距离可以无限缩小,输出\(“Forever love”\)(不含引号)。

输入输出样例

输入样例#1:

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

输出样例#1:

-2

说明

对于\(20\%\)数据,\(N \leq 10,M \leq 50\)

对于\(50\%\)数据,\(N \leq 300,M \leq 5000\)

对于全部数据,\(N \leq 1000,M \leq 10000,|W_i| \leq 100\),保证从节点\(1\)\(N\)有路径。

思路:题意就是让你在一张图上找一条从\(1\)号点到\(n\)号点的最短路径,如果这条路径可以无限缩小,那么就输出\(“Forever love”\),即存在负环,所以我们可以用\(spfa\)判断负环,如果一个点入队列超过\(n\)次,那么一定存在负环,这时直接输出\(“Forever love”\)并退出程序,然后spfa的过程中更新\(dis\)数组,即\(1\)号点到其它点的最短距离,然后这道题还有一个坑点就是距离不一定只有\(1\)号点能拉近,\(n\)号点也能,所以我们要用两遍\(spfa\),分别以\(1\)号点和\(n\)号点为起点,然后取两次\(dis[end]\)的最大值,其中\(end\)表示两次\(spfa\)的重点。

代码:

#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define maxn 1007
using namespace std;
int n,m,head[maxn],in[maxn],dis[maxn],num;
bool vis[maxn];
inline int qread() {
  char c=getchar();int num=0,f=1;
  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
  for(;isdigit(c);c=getchar()) num=num*10+c-'0';
  return num*f;
}
struct node {
  int v,w,nxt;
}e[20007];
inline void ct(int u, int v, int w) {
  e[++num].v=v;
  e[num].w=w;
  e[num].nxt=head[u];
  head[u]=num;
}
inline void spfa(int s) {
  memset(dis,0x3f,sizeof(dis));
  queue<int>q;
  q.push(s);
  dis[s]=0,in[s]=1,vis[s]=1;
  while(!q.empty()) {
    int u=q.front();q.pop();
    vis[u]=0;
    for(int i=head[u];i;i=e[i].nxt) {
      int v=e[i].v;
      if(dis[v]>dis[u]+e[i].w) {
        dis[v]=dis[u]+e[i].w;
        if(!vis[v]) {
          q.push(v),vis[v]=1;
          in[v]++;
          if(in[v]>n) {printf("Forever love\n");exit(0);} 
        }
      }
    }
  }
}
int main() {
  n=qread(),m=qread();
  for(int i=1,u,v,w;i<=m;++i) {
    u=qread(),v=qread(),w=qread();
    ct(u,v,-w);
  }
  spfa(1);int zrj=dis[n];
  spfa(n);int cyh=dis[1];
  printf("%d\n",min(zrj,cyh));
  return 0; 
}