题目背景
我是源点，你是终点。我们之间有负权环。 ——小明
题目描述
在小明和小红的生活中，有(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
");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
",min(zrj,cyh));
return 0;
}