Pagini recente » Cod sursa (job #748924) | Cod sursa (job #42794) | Cod sursa (job #841817) | Cod sursa (job #2448310) | Cod sursa (job #2400806)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50001
#define MMAX 2500001
#define INF 999999999
using namespace std;
int n, m;
struct edge{
int from, to, cost;
};
vector<edge> graph;
int dist[MMAX];
int vizited[NMAX];
bool bellmanFord(){
for(int i = 1; i <= m; i++){
dist[i] = INF;
vizited[i] = 0;
}
dist[1] = 0;
queue<int> q;
q.push(1);
while(!q.empty()){
int current = q.front();
vizited[current]++;
if(vizited[current] >= m){
return false;
}
for(int i = 0; i < m; i++){
int from = graph[i].from;
int to = graph[i].to;
int cost = graph[i].cost;
if(dist[from] != INF && dist[from] + cost < dist[to]){
dist[to] = dist[from] + cost;
q.push(i);
}
}
return true;
}
}
int main(){
ifstream be("bellmanford.in");
ofstream ki("bellmanford.out");
be >> n >> m;
edge w;
for(int i = 0; i < m; i++){
be >> w.from >> w.to >> w.cost;
graph.push_back(w);
}
bool ok = bellmanFord();
if(!ok){
ki << "Ciclu negativ!";
}
else{
for(int i = 2; i <= n; i++){
ki << dist[i] << " ";
}
}
}