Pagini recente » Rezultatele filtrării | Clasament selectie-vianu-2011 | Cod sursa (job #2802341)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const unsigned nmax = 100005;
struct edge{
int i;
int j;
int cost;
edge(int _i, int _j, int _cost): i(_i), j(_j), cost(_cost) {}
};
int main()
{
int N, M;
fin >> N >> M;
vector<edge> edges;
int distMin[nmax];
distMin[1] = 0;
for(int i = 2; i <= N; ++i)
distMin[i] = INT_MAX / 2;
for(int i = 1; i <= M; ++i)
{
int c, x, y;
fin >> c >> x >> y;
edges.push_back(edge(c, x, y));
}
for(int i = 0; i < N; ++i)
for(auto edge: edges)
distMin[edge.j] = min(distMin[edge.j], distMin[edge.i] + edge.cost);
for(int i = 0; i < M; ++i)
{
int ii = edges[i].i;
int j = edges[i].j;
int cost = edges[i].cost;
if(distMin[ii] + cost < distMin[j])
{
fout << "Ciclu negativ!";
return 0;
}
}
for(int i = 2; i <= N; ++i)
fout << distMin[i] << ' ';
return 0;
}