Bellman-Ford算法用于求单源最短路包含负权边的问题，还可以检测图中是否有负环

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false)
#define endl '\n'

using namespace std;
typedef long long ll;
typedef pair<int, int>p;

const int maxn = 205;
int n, m;
int d[maxn], pre[maxn];
struct E {
   
	int u, v, w;
}edge[maxn * maxn];

void init() {
   
	for (int i = 0;i <= n;++i)d[i] = INF;
}
int main() {
   
	while (~scanf("%d%d", &n, &m)) {
   
		init();
		for (int i = 1;i <= m;++i) {
   
			//无向图
			int x, y, z;cin >> x >> y >> z;
			edge[i].u = x;
			edge[i].v = y;
			edge[i].w = z;
			edge[i + m].u = y;
			edge[i + m].v = x;
			edge[i + m].w = z;
		}
		int s, t;
		scanf("%d%d", &s, &t);//起点和终点
		d[s] = 0;
		//Bellman-Ford核心代码
		for (int i = 0;i < n - 1;++i) {
   
			for (int i = 0;i < n;++i)pre[i] = d[i];
			for (int j = 1;j <= 2*m;++j) {
   
				if (d[edge[j].u] > d[edge[j].v] + edge[j].w)
					d[edge[j].u] = d[edge[j].v] + edge[j].w;
			}
			//小优化/
			int check = 0;
			for (int i = 0;i < n;++i)
				if (pre[i] != d[i]) {
   
					check = 1;
			}
			if (!check)break;
			//如果d数组和pre数组完全一样 说明不需要继续松弛 提前退出循环
		}
		//
		//若经过n-1轮松弛后最短路径仍然会变化 说明存在负环
		int flag = 0;
		for (int i = 1;i <= 2 * m;++i)
			if (d[edge[i].u] > d[edge[i].v] + edge[i].w)
				flag = 1;
		//
		if (flag)printf("此图存在负环");
		if (d[t] != INF)printf("%d\n", d[t]);
		else printf("-1\n");
	}
}