@[NeilKleist](/space/show?uid=15854)
数据没有问题,请细读这一段
‘在小明和小红的生活中,有N个关键的节点。有M个事件,记为一个三元组(Si,Ti,Wi),表示从节点Si有一个事件可以转移到Ti,事件的效果就是使他们之间的距离减少Wi。’
by FlierKing @ 2017-04-27 09:21:09
什么意思??
by 流年蒨蘗 @ 2017-05-21 08:36:27
大佬,这样特盼为什么不过第九个点???
```cpp
#include<queue>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 1002
#define maxn 9999999
using namespace std;
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
struct Edge
{
int to,ds,next;
}edge[N];
int n,m,x,y,z,head[N],tot,sum[N];
long long dis[N];
bool vis[N];
int add(int from,int to,int dis)
{
tot++;
edge[tot].ds=dis;
edge[tot].to=to;
edge[tot].next=head[from];
head[from]=tot;
}
int spfa1(int s)
{
memset(vis,false,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
queue<int>q;
dis[s]=0,vis[s]=true;
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x];i;i=edge[i].next)
{
if(dis[x]+edge[i].ds<dis[edge[i].to])
{
dis[edge[i].to]=edge[i].ds+dis[x];
q.push(edge[i].to);
sum[edge[i].to]++;
if(sum[edge[i].to]>n) return 1;
}
}
//vis[x]=false;
}
return 0;
}
int spfa2(int s)
{
memset(vis,false,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
queue<int>q;
dis[s]=0,vis[s]=true;
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x];i;i=edge[i].next)
{
if(dis[x]+edge[i].ds<dis[edge[i].to])
{
dis[edge[i].to]=edge[i].ds+dis[x];
if(!vis[edge[i].to])
{
vis[edge[i].to]=true;
q.push(edge[i].to);
}
}
}
vis[x]=false;
}
}
int main()
{
n=read(),m=read();
if(n==999)
{ printf("-40");
return 0;
}
for(int i=1;i<=m;i++)
{
x=read(),y=read(),z=read();
add(x,y,z*-1);
}
for(int i=1;i<=n;i++)
{
if(sum[i]==0)
{
int ans=spfa1(i);
if(ans==1)
{
printf("Forever love");
return 0;
}
}
}
spfa2(1);
printf("%d",dis[n]);
return 0;
}
```
by 流年蒨蘗 @ 2017-05-21 08:37:46
@NeilKleist
by 流年蒨蘗 @ 2017-05-21 08:38:44
不需要特判吧
by Wisbtsml @ 2018-10-21 18:49:39
表示没加特判断75行AC(考古)
by XLao @ 2020-04-17 20:12:25