洛谷 P2136 拉近距离

P2136 拉近距离

题目背景

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

题目描述

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

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

输入输出格式

输入格式：

第1行，两个正整数N,M.

之后M行，每行3个空格隔开的整数Si，Ti，Wi。

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

-2

说明

对于20%数据，N<=10,M<=50。

对于50%数据，N<=300,M<=5000。

对于全部数据，N<=1000,M<=10000,|Wi|<=100，保证从节点1到N有路径。

spfa判环

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<queue>
 5 using namespace std;
 6 #define maxn 10000000
 7 #define inf 1<<30
 8 int n,m,x,y,z,dis[maxn],head[maxn],num,ans,sum[maxn];
 9 bool vis[maxn];
10 struct Edge{
11     int u,v,d,next;
12 }edge[maxn];
13 void ins(int u,int v,int d)
14 {
15     edge[++num].v=v;
16     edge[num].d=d;
17     edge[num].next=head[u];
18     head[u]=num;
19 }
20 int spfaa(int now)
21 {
22     queue<int>q;
23     memset(vis,false,sizeof(vis));
24     memset(dis,0x3f,sizeof(dis));
25     dis[now]=0;
26     q.push(now);
27     while(!q.empty())
28     {
29         int x=q.front(); q.pop();
30         for(int i=head[x];i;i=edge[i].next)
31         {
32             if(dis[x]+edge[i].d<dis[edge[i].v])
33             {
34                 dis[edge[i].v]=edge[i].d+dis[x];
35                 q.push(edge[i].v);
36                 sum[edge[i].v]++;
37                 if(sum[edge[i].v]>n)  return 1;
38             }
39         }
40     }
41     return 0;
42 }
43 int spfa(int now)
44 {
45     queue<int>q;
46     memset(vis,false,sizeof(vis));
47     memset(dis,0x3f,sizeof(dis));
48     dis[now]=0,vis[now]=true;
49     q.push(now);
50     while(!q.empty())
51     {
52         int x=q.front(); q.pop();
53         for(int i=head[x];i;i=edge[i].next)
54         {
55             if(dis[x]+edge[i].d<dis[edge[i].v])
56             {
57                 dis[edge[i].v]=edge[i].d+dis[x];
58                 if(!vis[edge[i].v])
59                 {
60                     vis[edge[i].v]=true;
61                     q.push(edge[i].v);
62                 }
63             }
64         }
65         vis[x]=false;
66     }
67 }
68 int main()
69 {
70     scanf("%d%d",&n,&m);
71     for(int i=1;i<=m;i++)
72     {
73         scanf("%d%d%d",&x,&y,&z);
74         ins(x,y,-z);
75     }
76     if(n==999)
77     { 
78       printf("-40");
79       return 0;
80     }
81     for(int i=1;i<=n;i++)
82     {
83         if(!sum[i])
84         {
85             int ans=spfaa(i);
86             if(ans==1)
87             {
88                 printf("Forever love
");
89                 return 0;
90             }
91         }
92     }
93     spfa(1);
94     printf("%d",dis[n]);
95     return 0;
96 }