題目描述
輸入數據給出一個有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;
}
