基于DFS的SPFA判断负环
· 阅读需 1 分钟
inline bool spfa( int p,double mid )
{
vis[p]=true;
for( auto &[x,w]:rode[p] )
if( dis[x] > dis[p]+w-mid )
{
dis[x]=dis[p]+w-mid
if( vis[x] || spfa( x,mid ) ) return true;
}
vis[p]=false;
return false;
}
inline bool spfa( int p,double mid )
{
vis[p]=true;
for( auto &[x,w]:rode[p] )
if( dis[x] > dis[p]+w-mid )
{
dis[x]=dis[p]+w-mid
if( vis[x] || spfa( x,mid ) ) return true;
}
vis[p]=false;
return false;
}