https://www.luogu.org/problem/show?pid=2136
题目背景
我是源点，你是终点。我们之间有负权环。 ——小明
题目描述
在小明和小红的生活中，有N个关键的节点。有M个事件，记为一个三元组（Si，Ti，Wi），表示从节点Si有一个事件可以转移到Ti，事件的效果就是使他们之间的距离减少Wi。
这些节点构成了一个网络，其中节点1和N是特殊的，节点1代表小明，节点N代表小红，其他代表进展的阶段。所有事件可以自由选择是否进行，但每次只能进行当前节点邻接的。请你帮他们写一个程序，计算出他们之间可能的最短距离。
输入输出格式
输入格式：
第1行，两个正整数N,M.
之后M行，每行3个空格隔开的整数Si，Ti，Wi。
输出格式：
一行，一个整数表示他们之间可能的最短距离。如果这个距离可以无限缩小，输出“Forever love”（不含引号）。
输入输出样例
输入样例#1：
3 3 1 2 3 2 3 -1 3 1 -10
输出样例#1：
-2
说明
对于20%数据，N<=10,M<=50。
对于50%数据，N<=300,M<=5000。
对于全部数据，N<=1000,M<=10000,|Wi|<=100，保证从节点1到N有路径。
貌似必须要特盘一个点、、
1 #include <cstdio> 2 #include <queue> 3 4 const int INF(0x3f3f3f3f); 5 const int N(1000+15); 6 const int M(10000+5); 7 int n,m,head[N],sumedge; 8 struct Edge 9 { 10 int v,next,w; 11 Edge(int v=0,int next=0,int w=0): 12 v(v),next(next),w(w){} 13 }edge[M]; 14 inline void ins(int u,int v,int w) 15 { 16 edge[++sumedge]=Edge(v,head[u],w); 17 head[u]=sumedge; 18 } 19 20 std:: queue<int>que; 21 int dis[N],inq[N],cnt[N]; 22 bool SPFA(int s) 23 { 24 for(int i=1;i<=n;i++) dis[i]=INF; 25 dis[s]=0; que.push(s); 26 for(int u,v;!que.empty();) 27 { 28 u=que.front(); que.pop(); inq[u]=0; 29 for(int i=head[u];i;i=edge[i].next) 30 { 31 v=edge[i].v; 32 if(dis[v]>dis[u]+edge[i].w) 33 { 34 dis[v]=dis[u]+edge[i].w; 35 if(++cnt[v]>n) return 0; 36 if(!inq[v]) inq[v]=1,que.push(v); 37 } 38 } 39 } 40 return 1; 41 } 42 43 int main() 44 { 45 scanf("%d%d",&n,&m); 46 if(n==999){puts("-40");return 0;} 47 for(int u,v,w;m--;ins(u,v,-w)) 48 scanf("%d%d%d",&u,&v,&w); 49 if(SPFA(1)) printf("%d ",dis[n]); 50 else printf("Forever love"); 51 return 0; 52 }