NOIP2023模拟11联测32 百日草

本文主要是介绍NOIP2023模拟11联测32 百日草，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题解

有一个有$n$个点$m$条边的有向图，每条边上有一个正整数边权，你需要顺着图上的有向边从$1$号点走到$n$号点。

假设你经过的边边权依次为$w_1,w_2,\dots ,w_t$，则你的疲惫程度为$\underset{i=1}{\overset{t}{\max }}i\cdot w_i$，你需要找到最小疲惫程度的路径。

$2\le n,m\le 3\times 10^5,1\le w_i\le 10^9$

题解

我们可以二分答案$ans$。设$di{s}_i$表示从$1$号点到$i$号点要经过的最少边数（注意如果要从$u$经过边$i$到达$v$，则要满足$(di{s}_u+1)\times w_i\le ans$），那么用$\text{dijkstra}$即可求出所有能够从$1$号点到达的点的$dis$值，再判断能否到达$n$即可。

这样做时间复杂度为$O(n\log n\log v)$，其中$v$为$ans$的值域，也就是$m\max w_i$。下面考虑优化。

我们发现如果点$y$是从点$x$转移过来的，则$di{s}_y=di{s}_x+1$，于是我们可以将$\text{dijkstra}$改为$01\text{BFS}$，那么时间复杂度就降为$O(n\log v)$，就可以过了。

code

#include<bits/stdc++.h>
using namespace std;
const int N=300000;
int n,m,tot=0,d[N+5],l[N+5],r[N+5],z[N+5],dis[N+5];
long long w[N+5];
queue<int>q;
void add(int xx,int yy,int zz){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;w[tot]=zz;
}
bool check(long long mid){for(int i=1;i<=n;i++){z[i]=0;dis[i]=1e9;}dis[1]=0;q.push(1);while(!q.empty()){int u=q.front();q.pop();if(u==n) return 1;for(int i=r[u];i;i=l[i]){if((dis[u]+1)*w[i]>mid) continue;if(dis[u]+1<dis[d[i]]){dis[d[i]]=dis[u]+1;if(!z[d[i]]){z[d[i]]=1;q.push(d[i]);}}}}return 0;
}
int main()
{
//	freopen("zinnia.in","r",stdin);
//	freopen("zinnia.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1,x,y,z;i<=m;i++){scanf("%d%d%d",&x,&y,&z);add(x,y,z);}long long l=1,r=3e14,mid;while(l<=r){mid=l+r>>1;if(check(mid)) r=mid-1;else l=mid+1;}printf("%lld",r+1);return 0;
}

这篇关于NOIP2023模拟11联测32 百日草的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---