Pagini recente » Cod sursa (job #384399) | Cod sursa (job #435276) | Rezultatele filtrării | Cod sursa (job #2906300) | Cod sursa (job #2757813)
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <tuple>
using namespace std;
int N, M;
vector<vector<pair<int,int>>> Graph;
queue<int> Q;
bitset<50005> inQ;
vector<int> queueCount, DP;
void bellmanFord(int k)
{
DP[k] = 0;
Q.push(k);
inQ[k] = true;
++queueCount[k];
int v, cost;
while (!Q.empty()) {
k = Q.front(); Q.pop();
inQ[k] = false;
if (queueCount[k] > N) {
printf("Ciclu negativ!\n");
return;
}
for (auto it: Graph[k]) {
tie(v, cost) = it;
if (DP[v] > DP[k] + cost) {
DP[v] = DP[k] + cost;
if (!inQ[v]) {
Q.push(v);
inQ[v] = true;
}
++queueCount[v];
}
}
}
for (int i = 1; i < N; ++i)
printf("%d ", DP[i]);
printf("\n");
}
int main()
{
freopen("bellmanford.in", "r", stdin);
freopen("bellmanford.out", "w", stdout);
scanf("%d%d", &N, &M);
Graph.resize(N);
DP.resize(N, 0x3f3f3f3f);
queueCount.resize(N);
int from, to, cost;
for (int i = 0; i < M; ++i) {
scanf("%d%d%d", &from, &to, &cost);
--from; -- to;
Graph[from].emplace_back(to, cost);
}
bellmanFord(0);
return 0;
}