C++实现Bellmanford算法

#include<iostream>
#include<cctype>
#include<sstream>
#include<string>
#include<algorithm>
#include<map>
#include<cstring>
#include<cstdio>
#include<iomanip>
#include<vector>
#include<queue>

using namespace std;

const int INF = 100000000;

struct Node{
	int dist;
	int pre;

	Node() : dist(INF), pre(-1) {}
};

int main(void) {
	cout << "Bellmanford Algorithm for Directed Acyclic Graph: " << endl;

	while (true) {
		
		int nNodes;
		cout << "Number of Nodes: ";
		cin >> nNodes;

		vector<vector<int> > Wgt(nNodes, vector<int>(nNodes, INF));
		for (int i = 0; i < nNodes; ++i)
			Wgt[i][i] = 0;

		int nEdges;
		cout << "Number of Edges: ";
		cin >> nEdges;

		cout << "Src  Dest  Dist(< " << INF << "): " << endl;
		for (int i = 0; i < nEdges; ++i) {
			int src, dest, dist;
			cout << "[" << i << "]: ";
			cin >> src >> dest >> dist;
			Wgt[src][dest] = dist;
		}

		for (int i = 0; i < nNodes; ++i) {
			for (int j = 0; j < nNodes; ++j) {
				if (Wgt[i][j] != INF)
					cout << " " << setw(3) << Wgt[i][j];
				else
					cout << " " << "INF";
			}
			cout << endl;
		}

		//Bellmanford
		//INITIALIZE_SINGLE_SOURCE
		vector<Node> Rec(nNodes);
		Rec[0].dist = 0;
		//RELAX
		for (int k = 0; k < nNodes - 1; ++k)	//nNodes steps.
		for (int i = 0; i < nNodes; ++i) {
			for (int j = 0; j < nNodes; ++j) {
				if (Wgt[i][j] != INF)
					if (Rec[j].dist > Wgt[i][j] + Rec[i].dist) {
						Rec[j].dist = Wgt[i][j] + Rec[i].dist;
						Rec[j].pre = i;
					}
			}
		}
		//CHECK_WEIGHT
		for (int i = 0; i < nNodes; ++i) {
			for (int j = 0; j < nNodes; ++j) {			if (Wgt[i][j] != INF)
				if (Rec[j].dist > Wgt[i][j] + Rec[i].dist) {
					cout << "Negative weight circut." << endl;
				}
			}
		}

		
		for (int i = 0; i < nNodes; ++i) {
			cout << "[" << i << "]  Dist: " 
				<< Rec[i].dist << ", Pre: " << Rec[i].pre << endl;
		}

	}
	return 0;
}