Pagini recente » Cod sursa (job #435147) | Atasamentele paginii Clasament prega_oji2015_vi_4 | Borderou de evaluare (job #3172089) | Cod sursa (job #2683734)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int inf=1<<30;
ifstream be("bellmanford.in");
ofstream ki("bellmanford.out");
void bellmanford(int n,int m,int start,vector<vector<pair<int,int> > >&adj,vector<int>&dist)
{
dist[start]=0;
queue<int>q;
q.push(start);
bool negativcycles=false;
vector<bool>in_queue(n+1,false);
vector<int>cnt(n+1,0);
while(!q.empty() && !negativcycles)
{
int x=q.front();
q.pop();
in_queue[x]=false;
for(auto p:adj[x])
{
if(dist[x]<inf)
{
int edge=p.second;
int v=p.first;
if(dist[edge]>dist[x]+v)
{
dist[edge]=dist[x]+v;
if(!in_queue[edge])
{
if(cnt[edge]>=n)
negativcycles=true;
else
{
q.push(edge);
in_queue[edge]=true;
cnt[edge]++;
}
}
}
}
}
}
if(negativcycles){
ki<<"Ciclu negativ!"<<endl;
}
else
{
for(int i=2;i<=n;i++)
{
ki<<dist[i]<<" ";
}
ki<<endl;
}
}
int main()
{
int n,m;
be>>n>>m;
vector<vector<pair<int,int> > >adj(n+1);
for(int i=0;i<m;i++)
{
int x,y,cost;
be>>x>>y>>cost;
adj[x].push_back({cost,y});
}
vector<int>dist(n+1,inf);
bellmanford(n,m,1,adj,dist);
return 0;
}