CSP-J 2023 T4 旅游巴士 题解

· · 题解

Solution

只要会最短路即可轻松 AC 本题（

建立 k 层的分层图，由于边权为 1，可以用 bfs 跑最短路。

对于每条路，记录其路径长度 L 和路上最晚节点开放时间 T，则其从起点至终点的时间为 \left\lceil\dfrac{T-L}{k}\right\rceil\times k+L，可将其存在 dis_{L\bmod k,v} 中（路径的终点为 v）。

换句话说，我们维护一个 dis 数组，其中 dis_{j,i} 表示路径所需时间对 k 取模后为 j，路径的终点为 i 时的最小花费时间。

然后还有一个坑点：

题目中所给的 a_i 为道路开放时间，而由于道路还需要花费 1 的时间去走，所以将其转换为节点开放时间需要 +1。

最后输出 dis_{0,n} 即可。

时间复杂度 \mathcal{O}(\textsf{mk}(?))（最坏情况每条边被经过 k 次罢）。

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,y=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')y=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return x*y;
}
const int N=1e4+7,K=107,M=2e4+7;
ll n,m,k;
ll dis[K][N];
ll tot,nxt[M],head[N],to[M],val[M];
void add(ll u,ll v,ll w){
    nxt[++tot]=head[u];
    head[u]=tot;
    to[tot]=v;
    val[tot]=w;
}
struct node{
    ll L,T,id;
};
void bfs(){
    queue<node> q;
    q.push({0,0,1});
    memset(dis,-1,sizeof dis);
    dis[0][1]=0;
    while(!q.empty()){
        node u;
        u=q.front();
        q.pop();
        for(int j=head[u.id];j;j=nxt[j]){
            node v;
            v.L=u.L+1;
            v.T=max(u.T,(max(0ll,val[j]-v.L)-1+k)/k);
            v.id=to[j];
            if(dis[v.L%k][v.id]==-1||dis[v.L%k][v.id]>v.T*k+v.L){
                dis[v.L%k][v.id]=v.T*k+v.L;
                q.push(v);
            }
        }
    }
}
int main(){
    n=read();m=read();k=read();
    for(int i=1;i<=m;i++){
        ll u=read(),v=read(),w=read();
        add(u,v,w+1);
    }
    bfs();
    printf("%lld",dis[0][n]);
    return 0;
}