首页 > 代码库 > Easy sssp（spfa）
Easy sssp（spfa）
vijos 1053 Easy sssp
方法：用spfa判断是否存在负环
描述
输入数据给出一个有N(2 <= N <= 1,000)个节点，M(M <= 100,000)条边的带权有向图.
要求你写一个程序, 判断这个有向图中是否存在负权回路. 如果从一个点沿着某条路径出发, 又回到了自己, 而且所经过的边上的权和小于0, 就说这条路是一个负权回路.
如果存在负权回路, 只输出一行-1;
如果不存在负权回路, 再求出一个点S(1 <= S <= N)到每个点的最短路的长度. 约定: S到S的距离为0, 如果S与这个点不连通, 则输出NoPath.
格式
输入格式
第一行: 点数N(2 <= N <= 1,000), 边数M(M <= 100,000), 源点S(1 <= S <= N);
以下M行, 每行三个整数a, b, c表示点a, b(1 <= a, b <= N)之间连有一条边, 权值为c(-1,000,000 <= c <= 1,000,000)
输出格式
如果存在负权环, 只输出一行-1, 否则按以下格式输出
共N行, 第i行描述S点到点i的最短路:
如果S与i不连通, 输出NoPath;
如果i = S, 输出0;
其他情况输出S到i的最短路的长度.
样例1
样例输入1
6 8 11 3 41 2 63 4 -76 4 22 4 53 6 34 5 13 5 4Copy
样例输出1
064-3-27Copy
限制
Test5 5秒
其余 1秒
提示
做这道题时, 你不必为超时担心, 不必为不会算法担心, 但是如此“简单”的题目, 你究竟能ac么?
思路：哈哈，用spfa判断是否存在负环。
注意：1.要开long long 不然wa一个点
2.写读入优化，至少不用cin，cout
3.本题我在跑是否存在负环时，跑了两遍spfa，如果存在负环就不跑第二遍求最短路的那一遍了，第二遍spfa求最短路。
4.在判断负环是查询一个点被访问过几次，若被访问过n次，则说明存在负环。（他的思路和spfa一样！板子差不多）
代码：
#include<queue>#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 100010#define maxn 999999999using 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,s,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(dis,0x3f,sizeof(dis)); memset(vis,false,sizeof(vis)); queue<int>q; dis[s]=0,vis[s]=true; q.push(s); while(!q.empty()) { int x=q.front(); q.pop();vis[x]=false; for(int i=head[x];i;i=edge[i].next) { if(dis[x]+edge[i].ds<dis[edge[i].to]) { dis[edge[i].to]=dis[x]+edge[i].ds; sum[edge[i].to]++; q.push(edge[i].to); if(sum[edge[i].to]>n) return 1; } } } return 0;}void spfa2(int s)//{ memset(dis,0x3f,sizeof(dis)); memset(vis,false,sizeof(vis)); queue<int>q; dis[s]=0,vis[s]=true; q.push(s); while(!q.empty()) { int x=q.front(); q.pop();vis[x]=false; for(int i=head[x];i;i=edge[i].next) { if(dis[x]+edge[i].ds<dis[edge[i].to]) { dis[edge[i].to]=dis[x]+edge[i].ds; if(!vis[edge[i].to]) q.push(edge[i].to),vis[edge[i].to]=true; } } }}int main(){ n=read(),m=read(),s=read(); for(int i=1;i<=m;i++) { x=read(),y=read(),z=read(); add(x,y,z); } for(int i=1;i<=n;i++) { if(sum[i]==0) { int ans=spfa1(i); if(ans==1) { printf("-1"); return 0; } } } spfa2(s); for(int i=1;i<=n;i++) { if(dis[i]==0x3f3f3f3f3f3f3f3fll) printf("NoPath\n"); else printf("%lld\n",dis[i]); } return 0;}
Easy sssp（spfa）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。