[CSP-J 2023] 旅游巴士 题解

diamond_153 · 2023-10-21 20:46:15 · 个人记录

考场代码离正解只有一步……

首先，我们发现 n 与 k 范围很小，我们完全可以使用 O(nk) 级别的算法去做本题。于是我们二分答案（我就是这里右区间开小了），从终点用反图开始广搜，在每个景点模 k 意义下做标记，所以搜索时最多会做 nk 个标记，而且范围只有 10^6，完全可以接受。最后看 1 点处是否有 0 的标记即可（因为不在路上逗留，而且只要时间整除 k 就可以）。

代码：

#include<iostream>
#include<vector>
#include<utility>
#include<queue>
#include<list>
#include<string.h>
#define int long long
const int MaxN=1e4+100,MaxK=110;
bool chk[MaxN][MaxK];
int n,m,k,l=0,r=0,mid,mv;
std::vector<std::pair<int,int>> map[MaxN];
bool check(int tim){
    std::queue<std::pair<int,int>,std::list<std::pair<int,int>>> q;
    q.push({n,tim*k}),memset(chk,0,sizeof(chk));
    while(!q.empty()){
        std::pair<int,int> p=q.front();q.pop();
        if(chk[1][0])return 1;
        for(auto i:map[p.first])
            if(!chk[i.first][(p.second-1)%k]&&p.second>i.second)
                chk[i.first][(p.second-1)%k]=1,q.push({i.first,p.second-1});
    }
    return chk[1][0];
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin>>n>>m>>k;
    for(int i=0,u,v,a;i<m;i++){
        std::cin>>u>>v>>a;
        map[v].push_back({u,a});
        mv=r=std::max(r,(a+1)*n);
    }
    while(l<r)
        if(check(mid=(l+r)>>1))r=mid;
        else l=mid+1;
    std::cout<<(l!=0&&l!=mv?l*k:-1);
}