2025ICPC南昌邀请赛-G

G - Exploration

 题意如图

思路

首先可以发现在下取整的情况下x/a/b是等于x/(a*b)的（不太会证明但是小范围的打表可以证实这个结论），并且由于通道难度>=2，所以至多需要31条边即可使乘积达到1e9级别所以只需要用DP[i][j]维护从i出发，经过j-1条通道的最大乘积(超过1e9取1e9+10，目的是防止乘积爆longlong)，然后枚举经过几条通道即可知道最大乘积

代码实现

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define u1 (u<<1)
#define u2 (u<<1|1)
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18;
int n,m;
int h[N],ne[N],e[N],w[N],idx;
bool st[N];
void add(int a,int b,int c){e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dp[N][42];
void solve()
{	int q;memset(h,-1,sizeof h);cin>>n>>m>>q;_for(i,m){int a,b,c;cin>>a>>b>>c;add(a,b,c);}for(int i=1;i<=n;i++) dp[i][1]=1;for(int k=2;k<=33;k++){for(int i=1;i<=n;i++){	for(int j=h[i];~j;j=ne[j]){int u= e[j];dp[i][k]=max(dp[i][k],dp[u][k-1]*w[j]);dp[i][k]=min(dp[i][k],(int)1e9+10);}}	}while(q--){int a,b;cin>>a>>b;_rep(i,1,33){if(dp[a][i]>b){cout<<i-1<<'\n';break;}}}return ;
}
signed main()
{IOS;int T=1;
//	cin>>T;while(T--)solve();return 0;
}