记录编号	582223	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	Great Voyage	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	1.207 s
提交时间	2023-09-06 18:29:19	内存使用	5.61 MiB

#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second

using i64 = long long;
using pii = std::pair<int, int>;

const int maxn = 3e5 + 5, inf = 0x3f3f3f3f;
std::vector<pii> G[maxn];
int n, m, dis[maxn];

bool check(i64 x) {
	std::queue<int> q;
	memset(dis, 0x3f, sizeof(dis));
	q.emplace(1); dis[1] = 0;
	while(!q.empty()) {
		int u = q.front(); q.pop();
		if(u == n) return true;
		for(auto& [v, w] : G[u])
			if(dis[v] > dis[u] + 1&&1ll * (dis[u] + 1) * w <= x)
				dis[v] = dis[u] + 1, q.emplace(v);
	}
	return false;
}

int main() {
	freopen("great_voyage.in", "r", stdin);
	freopen("great_voyage.out", "w", stdout);
	scanf("%d %d", &n, &m); i64 l = 1, r = 0;
	for(int i = 1;i <= m;++ i) {
		int u, v, w; scanf("%d %d %d", &u, &v, &w);
		G[u].pb(v, w); r = std::max(r, (i64)w);
	}
	r = 1ll * r * m;
	while(l <= r) {
		i64 mid = l + (r - l >> 1);
		if(check(mid)) r = mid - 1;
		else l = mid + 1;
	}
	printf("%lld\n", l);
	return 0;
}