题面
问题描述
有一张 $n$ 个点 $m$ 条边的有向图，每条边上有一个正整数边权，你要顺着图上的有向边从 $1$ 号点走到 $n$ 号点。
假设你经过的边边权依次为 $w_1,w_2…w_t$，则你的疲惫程度为 $max^t_{i=1}i \cdot w_i$。你需要找到最小疲惫程度的路径。
输入格式
第一行两个空格分隔的正整数 $n,m$，表示有向图的点数和边数。有向图的点用 $1$ 到 $n$ 编号。
接下来 $m$ 行每行描述一条有向图的边，一行三个用空格分隔的正整数 $a,b,c$，表示一条从编号为 $a$ 的点出发，到达编号为 $b$ 的点，边权为 $c$ 的有向边。
可能有重边和/或自环。
输出格式
输出一个正整数，表示路径可能疲惫程度的最小值。
样例输入
3 3
1 2 5
2 3 4
1 3 6
样例输出
6
题解
考试的时候一开始看错题了，把疲惫程度看成了 $max^t_{i=1} w_i$，题面上的小样例竟然也能过qwq
题目要求最小疲惫程度的固定起止点的路径，因此我们可以很容易想到暴力的dfs解法，加上对边的 $vis$ 数组即可
但这样肯定会T掉，因为 $n,m$ 的大小在 $3 \times 10^5$，而dfs会对所有路径都跑一遍。我们发现这其中很多路径都是没有意义的，因为它们可能在很早就大于最终的答案了。
再一看题目，要求的是最大值最小，那么可否套一个二分上去呢？
我们试着二分一下答案，然后从 $1$ 号点开始bfs，此时能扩展的边就必须满足 $w \leq \frac{mid}{dep_i}$
这样就达到了 $\Theta (m log n)$ 的时间复杂度，显然可以通过。
另外，显然自环不会对答案产生贡献，因此可以在读入的时候忽略这些数据。
struct node{
int id,dep;
};
int vis[300030];
inline bool check(ll x){
memset(vis,0,sizeof vis);
queue<node> q;
q.push((node){1,0});
ll u,w,dep,v,maxw;
while(q.size()){
u=q.front().id;dep=q.front().dep+1;
if(u==n){
return true;
}
q.pop();
maxw=x/dep;
for(int id=hd[u];id;id=ed[id].nxt){
if(vis[id])continue;
v=ed[id].to;
w=ed[id].w;
if(w>maxw)continue;
q.push((node){v,dep});
vis[id]=1;
}
}
return false;
}
inline void solve(){
IO::read(n);
IO::read(m);
ll maxw=0;
for(ll i=1,u,v,w;i<=m;++i){
IO::read(u);IO::read(v);IO::read(w);
adde(u,v,w);maxw=max(maxw,w);
}
ll l=1,r=(ll)maxw*n+1,ans,mid;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
IO::putln(ans);
}