#include<bits/stdc++.h>
const int inf=0x3f3f3f3f;
const int maxn=1e5+;
struct edge{
int u,v;//两个点
int w; //权值
Edge(int _u = , int _v = , int _w = ): u(_u), v(_v), w(_w) {}
};
int dis[maxn];//松弛更新数组
vector<edge>e;//用容器存边
//如果存在从源点可达的权为负的回路。则 应为无法收敛而导致不能求出最短路径
int bellman_ford(int s,int n)
{
memset(dis,inf,sizeof(dis));
dis[s]=;
//最多做n-1次
for(int i=;i<n;i++)
{
int flag=;
for(int j=; j<int(e.size()); j++)
{
if(dis[e[j].v] > dis[e[j].u] + e[j].w)
{
dis[e[j].v] = dis[e[j].u] + e[j].dis;
flag=;
}
}
if(flag==) return ;//没有负权回路
}
//有负权回路
for(int j=; j < int(e.size()); j++)
{
if(dis[e[j].v] > dis[e[j].u] + e[j].w)
return ;
} return ;
}