Bellman-Ford

#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];
	}
}