首页 > 代码库 > P2136 拉近距离（spfa判负环）
P2136 拉近距离（spfa判负环）
洛谷—— P2136 拉近距离
题目背景
我是源点，你是终点。我们之间有负权环。 ——小明
题目描述
在小明和小红的生活中，有N个关键的节点。有M个事件，记为一个三元组（Si，Ti，Wi），表示从节点Si有一个事件可以转移到Ti，事件的效果就是使他们之间的距离减少Wi。
这些节点构成了一个网络，其中节点1和N是特殊的，节点1代表小明，节点N代表小红，其他代表进展的阶段。所有事件可以自由选择是否进行，但每次只能进行当前节点邻接的。请你帮他们写一个程序，计算出他们之间可能的最短距离。
输入输出格式
输入格式：
第1行，两个正整数N,M.
之后M行，每行3个空格隔开的正整数Si，Ti，Wi。
输出格式：
一行，一个整数表示他们之间可能的最短距离。如果这个距离可以无限缩小，输出“Forever love”（不含引号）。
输入输出样例
输入样例#1：
3 31 2 32 3 -13 1 -10
输出样例#1：
-2
说明
对于20%数据，N<=10,M<=50。
对于50%数据，N<=300,M<=5000。
对于全部数据，N<=1000,M<=10000,|Wi|<=100，保证从节点1到N有路径。
思路：
注意在输入的时候要输入z*-1！！！！
这个题我们可以这样考虑：如果一个图存在负权环，那样这个图的最短路可以被无限更新。
所以，这个题我们就可以简单的处理成一个用spfa判断负环的问题了！
最后一个点特判！！
代码：
#include<queue>#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#define N 1002#define maxn 9999999using 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*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(); for(int i=1;i<=m;i++) { x=read(),y=read(),z=read(); add(x,y,z*-1); } if(n==999) { printf("-40"); return 0; } 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;}
P2136 拉近距离（spfa判负环）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。