---
tags: codebook
---

{%hackmd theme-dark %}

# Label Correcting Algorithm(SPFA)

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define endl '\n'
using namespace std;
constexpr int limit = numeric_limits<int>::max();
struct LabelCorrectingAlgorithm {
	vector<int> d;
	vector<size_t> parent;
	vector<size_t> operator()(size_t x) {
		vector<size_t> v;
		do v.push_back(x), x = parent[x]; while (x != parent[x]);
		return v;
	}
	LabelCorrectingAlgorithm(const vector<vector<pair<size_t, int>>>& v, size_t source = 0):
		d(v.size(), numeric_limits<int>::max()), parent(v.size(), 0) {
		d[source] = 0;
		queue<size_t> q; q.push(source);
		vector<bool> inqueue(v.size(), false);
		while (!q.empty()) {
			auto a = q.front();
			q.pop(), inqueue[a] = false;
			if (inqueue[parent[a]]) continue;
			for (const auto& i : v[a])
				if (i.second != limit && d[a] != limit && d[a] + i.second < d[i.first]) {
					d[i.first] = d[a] + i.second;
					parent[i.first] = a;
					if (!inqueue[i.first])
						q.push(i.first), inqueue[i.first] = true;
				}
		}
	}
};
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	for (const auto& i : v)
		os << i << ' ';
	return os;
}
int main() {
//	cin.tie(nullptr);
//	ios::sync_with_stdio(false);
	int c; size_t n, m, a, b;
	cin >> n >> m;
	vector<vector<pair<size_t, int>>> v(n + 1);
	for (size_t i = 0; i != m; i++)
		cin >> a >> b >> c, v[a].emplace_back(b, c);
	LabelCorrectingAlgorithm graph(v, 4);
	for (size_t i = 1; i != v.size(); i++)
		cout << i << ": " << graph(i) << endl;
	return 0;
}