[kuangbin带你飞] 题单 最短路问题 + 并查集问题模板题及简单题 https://blog.csdn.net/m0_46272108/article/details/108923142
Floyd原理推荐可以看看这篇：https://blog.csdn.net/m0_46272108/article/details/108919125
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define ll long long //#define int ll #define INF 0x3f3f3f3f using namespace std; int read() { int w = 1, s = 0; char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') w = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); } return s * w; //最大公约数 }int gcd(int x,int y) { if(x<y) swap(x,y);//很多人会遗忘，大数在前小数在后 //递归终止条件千万不要漏了，辗转相除法 return x % y ? gcd(y, x % y) : y; } int lcm(int x,int y)//计算x和y的最小公倍数 { return x * y / gcd(x, y);//使用公式 } //------------------------ 以上是我常用模板与刷题几乎无关 ------------------------// const int N = 510; int n, m, w; int dis[N][N]; bool Floyd() { bool flag = 0; //弗洛伊德核心思想 for (int k = 1; k <=n ; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { //当i，j的原来的边的最短距离，大于经过k点所到达的距离那么就替换。 if (dis[i][k] + dis[k][j] <= dis[i][j]) { dis[i][j] = dis[i][k] + dis[k][j]; } } if (dis[i][i] < 0) { flag = 1; break; } } if (flag) break; } return flag; } int main() { int tt = read(); while (tt--) { n = read(), m = read(), w = read(); //初始化为最大值 for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) dis[i][j] = dis[j][i] = INF; for (int i = 1; i <= m; ++i) { int s = read(), e = read(), t = read(); if (dis[s][e] < t) continue; dis[s][e] = dis[e][s] = t; } for (int i = 1; i <= w; ++i) { int s = read(), e = read(), t = read(); dis[s][e] = -t; } if (Floyd()) printf("YES\n"); else printf("NO\n"); } }