Pagini recente » Cod sursa (job #44151) | Cod sursa (job #2409134) | Cod sursa (job #92699) | Cod sursa (job #2980384) | Cod sursa (job #990621)
Cod sursa(job #990621)
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <climits>
#define mp make_pair
#define pb push_back
using namespace std;
const int inf=INT_MAX/2;
int n,m,D[50001];
vector< pair <int,int> > lv[50001];
int times_used[ 50001 ],negative;
void make_GRAPH()
{
scanf("%d%d", &n, &m);
int a,b,c,i;
for(i = 1; i <= m; ++i){
scanf("%d%d%d",&a,&b,&c);
lv[ a ].pb(mp(b,c));
}
}
void Bellman_Ford()
{
vector< pair<int,int> > ::iterator it;
queue<int> Q;
int k;
for(int i = 2; i <= n; ++i)
D[ i ] = inf;
Q.push(1);
while(!Q.empty()&& !negative){
k = Q.front();Q.pop();
for(it = lv[k].begin(); it != lv[k].end(); ++it)
if(D[it->first] > D[k] + it->second)
{
D[ it->first ] = D[k] + it->second;
times_used[ it->first ]++;
Q.push(it->first);
if(times_used[ it->first ] > n)negative = 1;
}
}
}
void Print()
{
if(negative == 1)
printf("Ciclu negativ!\n");
else{
for(int i=2; i<=n; ++i)
if(D[i] != inf)
printf("%d ",D[i]);
else printf("0 ");
}
}
int main()
{
freopen( "dijkstra.in", "r", stdin);
freopen( "dijkstra.out", "w", stdout);
make_GRAPH();
Bellman_Ford();
Print();
return 0;
}