可以解决有负权边的图，但不能解决有负权回路的图(有负权回路的最短路本来就不存在嘛)
思路：
假设一共有n个点
那么从u~v最多经过n-1个点便肯定能找出最短边(因为最多把其他的点全走一遍就知道最短路径了)
所以算法就是：
从u(起点)出发，经过1个点到v点试试，如果更加小，就更新一下dist
再经过2个点到v点试试，如果更加小，就更新一下dist
.........
当经过n-1个点时，此时dist中就是从u点出发到各点的最短路径
判断有无负权回路的方法：
再试着从u点出发，更新所有其他点的dist，如果能更新就肯定有负权环
因为此时u点到v点经过了n个点，肯定有个点是经过2次的，而经过这个点2从比经过1次路径更加短，所以肯定有负权环
代码如下：
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int INF=(1<<30);
const int maxn=1000+5;
struct Edge{int from,to,weight;Edge(int f,int t,int w):from(f),to(t),weight(w){}
};
vector<Edge> edges;
int dist[maxn];
bool Bellman_ford(int s,int n)
{for(int i=0;i<n;i++) dist[i]=INF;dist[s]=0;for(int k=1;k<n;k++) //从u~v点经过k条边for(int i=0;i<edges.size();i++){int u=edges[i].from;int v=edges[i].to;int w=edges[i].weight;dist[v]=min(dist[v],dist[u]+w);}for(int i=0;i<edges.size();i++){ //判断有无负环 int u=edges[i].from;int v=edges[i].to;int w=edges[i].weight;if(dist[v]>dist[u]+w) return true;} return false;
}
int main()
{int T;cin>>T;while(T--){int N,M;cin>>N>>M; //M条边 int u,v,w;edges.clear();while(M--){cin>>u>>v>>w;edges.push_back(Edge(u,v,w));edges.push_back(Edge(v,u,w));}cout<<(Bellman_ford(1,N)?"YES":"NO")<<endl; //判断有无负环 }return 0;
}