求加团:https://www.luogu.com.cn/team/90259

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int x, step;
};
int n, m, u, v1, w, d[1505][1505], b[1505][1505];
bool v[1505];
queue<node> q;
int bfs()
{
	int ans = 0xcfcfcfcf;
	q.push({1, 0});
	v[1] = 1;
	while(!q.empty())
	{
		node u = q.front();
		q.pop();
		for(int i = 1; i <= n; i++)
		{
			if(i == u.x || b[u.x][i] == 0 || v[i] == 1) continue;
			v[i] = 1;
			q.push({i, u.step + d[u.x][i]});
			ans = max(ans, u.step + d[u.x][i]);
			if(i == n) return ans;
		}
	}
	return -1;
}
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		cin >> u >> v1 >> w;
		b[u][v1] = 1;
		d[u][v1] = w;
	}
	cout << bfs();
	return 0;
}