描述
输入数据给出一个有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的最短路的长度.
输入
6 8 1 1 3 4 1 2 6 3 4 -7 6 4 2 2 4 5 3 6 3 4 5 1 3 5 4
输出
0 6 4 -3 -2 7
思路：spfa算法，不过这道题存在陷阱。第一存在重边，解决方法用邻接矩阵表示图，保留权值最小的一个。第二图可能不连通，解决方法对每个结点进行spfa，为了优化时间，设置一个used数组标志已经遍历过的结点，遍历过的结点无需再进行spfa。最后加上若d[s]<0则存在负环。
#include<cstdio> #include<cstring> #include<queue> using namespace std; const int MAXN=1005; const int INF=0x7f7f7f7f; int n,m,s; int contain; int mp[MAXN][MAXN]; int d[MAXN]; int cnt[MAXN]; bool vis[MAXN],used[MAXN]; void addedge(int u,int v,int w) { if(mp[u][v]>w) mp[u][v]=w; } bool spfa(int scource) { for(int i=1;i<=n;i++) { d[i]=INF; vis[i]=false; } queue<int> que; que.push(scource); vis[scource]=true; used[scource]=true; d[scource]=0; while(!que.empty()) { int now = que.front();que.pop(); vis[now]=false; for(int i=1;i<=n;i++) { if(now==i||mp[now][i]==INF) continue; if(d[i]>d[now]+mp[now][i]) { d[i]=d[now]+mp[now][i]; if(d[scource]<0) return true; if(!vis[i]) { used[i]=vis[i]=true; que.push(i); cnt[i]++; if(cnt[i]>=n) return true; } } } } return false; } void solve() { for(int i=1;i<=n;i++) { if(!used[i]&&spfa(i)) { printf("-1 "); return ; } } if(spfa(s)) { printf("-1 "); } else { for(int i=1;i<=n;i++) if(d[i]==INF) printf("NoPath "); else printf("%d ",d[i]); } } int main() { scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j) mp[i][j]=0; else mp[i][j]=mp[j][i]=INF; for(int i=0;i<m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); } solve(); return 0; }
spfa+前向星可解决重边问题。d[source][source]<0则存在负环
#include <cstdio> #include <cstring> #include <queue> using namespace std; const int MAXN=1005; const int INF=0x3f3f3f3f; struct Edge{ int to,w,next; }es[100005]; int head[MAXN],tot; int n,m,source; int d[MAXN][MAXN],vis[MAXN],used[MAXN]; void addedge(int u,int v,int w) { es[tot].to=v; es[tot].w=w; es[tot].next=head[u]; head[u]=tot++; } bool spfa(int s) { for(int i=1;i<=n;i++) { d[s][i]=INF; vis[i]=0; } queue<int> que; que.push(s); d[s][s]=0; vis[s]=1; used[s]=1; while(!que.empty()) { int u=que.front();que.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=es[i].next) { Edge e=es[i]; if(d[s][e.to]>d[s][u]+e.w) { d[s][e.to]=d[s][u]+e.w; if(d[s][s]<0) return true; if(!vis[e.to]) { que.push(e.to); vis[e.to]=1; used[e.to]=1; } } } } return false; } void solve() { if(spfa(source)) { printf("-1 "); return ; } for(int i=1;i<=n;i++) { if(!used[i]&&spfa(i)) { printf("-1 "); return ; } } for(int i=1;i<=n;i++) { if(d[source][i]==INF) printf("NoPath "); else printf("%d ",d[source][i]); } } int main() { memset(head,-1,sizeof(head)); scanf("%d%d%d",&n,&m,&source); for(int i=0;i<m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); } solve(); return 0; }