# Bellman-Ford

user_3763047219
c_cpp
2 years ago
1.3 kB
1
Indexable
Never
```#include <iostream>

int main()
{
int n = 0, m = 0;
static int E[201][2] = {};
float w[201] = {};
int s = 0;

scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d %d %f", &E[i][0], &E[i][1], &w[i]);
}
scanf("%d", &s);
float key[51] = {};
for (int i = 1; i <= n; i++) {//記得要把key都先設成無限大
key[i] = 999999;
}
key[s] = 0;
int parent[51] = {0};
//全部邊都要update 重複n-1次
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m; j++) {
if (key[E[j][1]] > key[E[j][0]] + w[j]) {
key[E[j][1]] = key[E[j][0]] + w[j];
parent[E[j][1]] = E[j][0];
}
}
}
float sum1 = 0;
for (int i = 1; i <= n; i++) {
sum1 = sum1 + key[i];
}

for (int j = 1; j <= m; j++) {
if (key[E[j][1]] > key[E[j][0]] + w[j]) {
key[E[j][1]] = key[E[j][0]] + w[j];
}
}
float sum2 = 0;
for (int i = 1; i <= n; i++) {
sum2 = sum2 + key[i];
}

if (sum1 != sum2) {
printf("There is a negative weight cycle in the graph");
}
else {
for (int i = 1; i < n; i++) {
std::cout << key[i] << " ";
}
std::cout << key[n];
std::cout << "\n";
for (int i = 1; i < n; i++) {
std::cout << parent[i] << " ";
}
std::cout << parent[n];
}
}```