Pagini recente » Cod sursa (job #511968) | Monitorul de evaluare | Monitorul de evaluare | Rezultatele filtrării | Cod sursa (job #1089658)
/*
~Keep It Simple!~
*/
#include<stdio.h>
#include<list>
#define NMax 50005
#define inf 1000000000
using namespace std;
int N,M,n;
list< pair<int,int> > G[NMax];
int Dist[NMax],Heap[NMax],Poz[NMax];
bool viz[NMax];
void GoDown(int node)
{
int aux, x = 0;
while( x!=node )
{
x = node;
if( x*2 <= n && Dist[Heap[node]]>Dist[Heap[x*2]] ) node = x*2;
if( x*2+1 <=n && Dist[Heap[node]]>Dist[Heap[x*2+1]] ) node = x*2+1;
aux = Heap[x];
Heap[x] = Heap[node];
Heap[node] = aux;
Poz[Heap[x]] = x;
Poz[Heap[node]] = node;
}
}
void RemoveFromHeap()
{
Poz[Heap[1]] = -1;
Heap[1] = Heap[n--];
Poz[Heap[1]] = 1;
GoDown(1);
}
void Update( int node )
{
int aux;
while(node/2 && Dist[Heap[node/2]] > Dist[Heap[node]])
{
aux = Heap[node];
Heap[node] = Heap[node/2];
Heap[node/2] = aux;
Poz[Heap[node]] = node;
Poz[Heap[node/2]] = node/2;
node/=2;
}
}
void Insert(int node)
{
Heap[++n] = node;
Poz[node] = n;
Update(n);
}
void BellManFord()
{
for(int i=2; i<=N; i++)
{
Dist[i] = inf;
Heap[i] = Poz[i] = i;
}
Heap[1] = Poz[1] = 1;
int Source;
Insert(1);
long long idx = 0;
while ( n && (idx < 1LL*N*M))
{
idx++;
Source = Heap[1];
RemoveFromHeap();
viz[Source] = 0;
for(list< pair<int,int> >::iterator it = G[Source].begin(); it!=G[Source].end(); it++)
{
if(Dist[Source]+it->second < Dist[it->first])
{
Dist[it->first] = Dist[Source] + it->second;
if( !viz[it->first] )
{
viz[it->first] = 1;
Insert(it->first);
}
}
}
}
}
int Ciclu_Negativ()
{
for(int i=1; i<=N; i++)
for(list<pair<int,int>>::iterator it = G[i].begin(); it!=G[i].end(); it++)
if( Dist[i] + it->second < Dist[it->first] )
return 1;
return 0;
}
int main()
{
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
scanf("%d%d",&N,&M);
int x,y,c;
for(int i=1; i<=M; i++)
{
scanf("%d%d%d",&x,&y,&c);
G[x].push_back(make_pair(y,c));
}
BellManFord();
if( Ciclu_Negativ() )
{
printf("Ciclu negativ!");
}
else
{
for(int i=2; i<=N; i++)
printf("%d ",Dist[i]);
}
}