bellman-ford.cc

#include <iostream>
#include <stdint.h>
#include <stdlib.h>
using namespace std;
 
const size_t SIZE = 100;
 
int64_t V[SIZE], E[SIZE][SIZE];
 
int main() {
	for(int i = 0; i < SIZE; i++)
		for(int j = 0; j < SIZE; j++)
			E[i][j] = INT64_MAX;
 
	for(int i = 0; i < SIZE; i++)
		V[i] = INT64_MAX;
 
	// |V| = N, |E| = M
	int N, M;
	cin >> N >> M;
 
	int start, end;
	cin >> start >> end;
 
	// input format: endpoint_a endpoint_b cost
	for(int i = 0; i < M; i++) {
		int a, b, cost;
		cin >> a >> b >> cost;
		E[a][b] = E[b][a] = cost;
	}
 
	V[start] = 0;
 
	int cnt = 0;
	bool updated = true;
	while(updated && cnt++ <= N) {
		updated = false;
		for(int i = 0; i < N; i++) {
			if(V[i] == INT64_MAX)
				continue;
			for(int j = 0; j < N; j++) {
				if(i == j || E[i][j] == INT64_MAX)
					continue;
				if(V[j] > E[i][j] + V[i]) {
					V[j] = E[i][j] + V[i];
					updated = true;
				}
			}
		}
 
		if(!updated)
			break;
	}
 
	if(updated)
		cout << -1 << '\n'; // the graph has negative-weight cycle
	else
		cout << V[end] << '\n';
}