题解

代码：

#include <bits/stdc++.h>
using namespace std;
int n, m;
struct str
{
	int u, v, w;
};
vector<str> st;
long long d[100001];
bool b()
{
	for(int i = 1; i<=n; i++)
	{
		bool b = false;
		for(int i = 0; i<=m-1; i++)
		{
			str a = st[i];
			if(d[a.u]+a.w<d[a.v])
			{
				d[a.v]=d[a.u]+a.w;
				b=true;
			}
		}
		if(i==n && b)
		{
			return true;
		}
	}
	return false;
}
int main() 
{
    cin >> n >> m;
    for(int i = 1; i<=m; i++)
    {
    	int u, v, w;
    	cin >> u >> v >> w;
    	st.push_back({u, v, w});
	}
	if(b())
	{
		cout << "Possible" << endl;
	}
	else
	{
		cout << "Not possible" << endl;
	}
    return 0;
}

利用 Bellman-Ford 求负环 有就输出Possible, 否则输出Not possible