Pagini recente » Cod sursa (job #1227712) | Cod sursa (job #712692)
Cod sursa(job #712692)
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define dim 50005
vector <pair <int,int> > v[dim];
int viz[dim], d[dim], use[dim], n, m,ok;
queue <int> q;
void read()
{
int i, a, b, c;
fin>>n >>m;
for(i=1;i<=m;++i)
{
fin>>a >>b >>c;
v[a].pb(mp(b,c));
}
}
void solve()
{
vector <pair <int,int> > ::iterator it;
memset(d,inf,sizeof(d));
int nod;
q.push(1);
d[1]=0;
use[1]=1;
while(!q.empty())
{
nod=q.front();
viz[nod]=0;
for(it=v[nod].begin();it!=v[nod].end();++it)
{
if(d[nod]+it->sc < d[it->fs])
{
d[it->fs]= d[nod]+it->sc;
if(viz[it->fs]==0)
{
viz[it->fs]=1;
q.push(it->fs);
}
if(++use[it->fs]==n)
{
ok=1;
return ;
}
}
}
q.pop();
}
}
void print()
{
if(ok==1)
fout<<"Ciclu negativ!";
else
for(int i=2;i<=n;++i)
fout<<d[i] <<" ";
}
int main()
{
read();
solve();
print();
return 0;
}