P9751 [CSP-J 2023] 旅游巴士
本题主要的难点在于到达和离开景区的时间都必须是 \(k\) 的非负整数倍以及每条道路均设置了一个 “开放时间” \(a_i\)。
对于第一个限制，只需要拆点，将每个点拆成距离 \(\bmod k=0\sim k-1\)。
对于第二个限制，发现求的是最小值，答案具有二段性，可二分。二分之后，就可以从终点往起点推，由于越晚可以走的边越多，此时可以贪心的求，类似最短路，到达起点看一下能到且距离大于等于 \(0\)。
可以发现图最多有 \(nk\) 个点，所以答案是在 \(nk\) 量级以内，二分时的复杂度是 \(O(\log n)\)（因为必须是 \(k\) 的倍数），check 需要 bfs，复杂度 \(O(nk)\)，所以总复杂度是 \(O(nk\log n)\)。
#include<iostream>
#include<cstring>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
const int N=10010,M=20010,K=110;
int n,m,k,h[N],e[M],ne[M],w[M],idx,dis[N][K];
typedef pair<int,int> pii;
pii q[N*K];//don't forget memset h!
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool check(int mid){
// cout<<mid<<'\n';
memset(dis,-0x3f,sizeof dis);
dis[n][0]=mid;
int hh=0,tt=0;
q[tt++]={n,0};
Wh(hh!=tt){
auto p=q[hh++];
int x=p.first,y=p.second;
// cout<<x<<' '<<y<<' '<<dis[x][y]<<'\n';
Ed{
int j=e[i],we=w[i],ne=y?y-1:k-1;
if(dis[x][y]>we&&dis[j][ne]<dis[x][y]-1){
dis[j][ne]=dis[x][y]-1;
q[tt++]={j,ne};
}
}
}
return dis[1][0]>=0;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
#ifdef ONLINE_JUDGE
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#endif
cin>>n>>m>>k;
memset(h,-1,n*4+4);
W(m){
int a,b,c;
cin>>a>>b>>c;
add(b,a,c);
}
int l=0,r=(2e6+100)/k;
Wh(l<r){
// cout<<l<<' '<<r<<'\n';
int mid=l+r>>1;
if(check(mid*k))r=mid;
else l=mid+1;
}
// cout<<l<<' '<<r<<'\n';
if(!check(r*k))cout<<"-1\n";
else cout<<r*k<<'\n';
return 0;
}