题目描述
输入数据给出一个有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的最短路的长度.
这个题真是异常的坑 打着题目是sssp的表面而实地里却隐藏这一刻spfa的心(貌似不通) 下面讲一下spfa的详细操作步骤(和dijkstra应该很像):
g[i][j]表示邻接矩阵 dist[i]表示源点到i的距离 cnt[i]表示点i的入队次数 v[i]表示i这个点是否在队列中
初始化:v[]数组赋值为false cnt[]=0 把所有点与源点的距离变为很大
接着 把源点入队 再把dist[start]变为0
然后做和bfs差不多的操作 拓展队首的点 更新新的最短的距离......
如果某个点的入队次数>n那么一定有负环 证明:如果一个点存在正的最短路 那么他最多可以和其他所有点连而拓展n次 而如果是负环 那么他的这个最短路中如果有负环 那么就会越拓展越小 当然入队就会超过n次
这里还有一个地方要注意 就是判负环 因为这个负环不一定在源点的路上 那么是不是应该把所有点都找过去呢 显然不是 这里有两个方法 推荐第二种做法:
用dfs找连通块 然后对每一个联通块做SPFA
受zbt大神的指点 可以加一个入度为0 只有出边并连着除他外所有点 那么只要对这个点进行拓展就可以找到所有的负环
最后还有一点就是我这样做在vijos里只有50分 粗部估计是这个邻接矩阵的问题 最好改成边集数组来做 代码下次给
代码如下:
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=1000+10;
long long g[maxn][maxn],dist[maxn],cnt[maxn];
bool v[maxn],used[maxn];
int n,m,s;
int a,b,c;
queue<int>q;
bool SPFA(int start)
{
for(int i=1;i<=n;i++)
{
dist[i]=0x7f7f7f;
cnt[i]=0;
v[i]=false;
}
while(!q.empty())
q.pop();
v[start]=true;
q.push(start);
dist[start]=0;
while(!q.empty())
{
int x=q.front();
q.pop();
v[x]=false;
for(int k=1;k<=n;k++)
if(g[x][k]<0x7f7f7f&&dist[x]+g[x][k]<dist[k])
{
dist[k]=dist[x]+g[x][k];
// used[k]=true;
if(!v[k])
{
cnt[k]++;
if(cnt[k]>n)
return false;
v[k]=true;
q.push(k);
}
}
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
// freopen("1.in","r",stdin);
cin>>n>>m>>s;
for(int i=1;i<=n+1;i++)
for(int j=1;j<=n+1;j++)
g[i][j]=0x7f7f7f;
for(int i=1;i<=m;i++)
{
cin>>a>>b>>c;
if(c<g[a][b])
g[a][b]=c;
}
for(int i=1;i<=n;i++)
g[n+1][i]=1;
// for(int i=1;i<=n;i++)
// {
// for(int j=1;j<=n;j++)
// cout<<g[i][j]<<' ';
// cout<<endl;
// }
// for(int i=1;i<=n;i++)
// {
// if(!SPFA(i))
// {
// cout<<-1<<endl;
// return 0;
// }
// }
if(!SPFA(n+1))
{
cout<<-1<<endl;
return false;
} SPFA(s);
for(int i=1;i<=n;i++)
{
if(dist[i]==0x7f7f7f)
{
cout<<"NoPath"<<endl;
continue;
}
cout<<dist[i]<<endl;
}
return 0;
}