CSP

2024-02-04 04:10| 来源: 网络整理| 查看: 265

[CSP-J 2023] 旅游巴士【民间数据】题目描述

小 Z 打算在国庆假期期间搭乘旅游巴士去一处他向往已久的景点旅游。

旅游景点的地图共有 n n n 处地点，在这些地点之间连有 m m m 条道路。其中 1 1 1 号地点为景区入口， n n n 号地点为景区出口。我们把一天当中景区开门营业的时间记为 0 0 0 时刻，则从 0 0 0 时刻起，每间隔 k k k 单位时间便有一辆旅游巴士到达景区入口，同时有一辆旅游巴士从景区出口驶离景区。

所有道路均只能单向通行。对于每条道路，游客步行通过的用时均为恰好 1 1 1 单位时间。

小 Z 希望乘坐旅游巴士到达景区入口，并沿着自己选择的任意路径走到景区出口，再乘坐旅游巴士离开，这意味着他到达和离开景区的时间都必须是 k k k 的非负整数倍。由于节假日客流众多，小 Z 在旅游巴士离开景区前只想一直沿着景区道路移动，而不想在任何地点（包括景区入口和出口）或者道路上停留。

出发前，小 Z 忽然得知：景区采取了限制客流的方法，对于每条道路均设置了一个 “开放时间” a i a _ i ai，游客只有不早于 a i a _ i ai 时刻才能通过这条道路。

请帮助小 Z 设计一个旅游方案，使得他乘坐旅游巴士离开景区的时间尽量地早。

输入格式

输入的第一行包含 3 个正整数 n , m , k n, m, k n,m,k，表示旅游景点的地点数、道路数，以及旅游巴士的发车间隔。

输入的接下来 m m m 行，每行包含 3 个非负整数 u i , v i , a i u _ i, v _ i, a_ i ui,vi,ai，表示第 i i i 条道路从地点 u i u _ i ui 出发，到达地点 v i v _ i vi，道路的“开放时间”为 a i a _ i ai。

输出格式

输出一行，仅包含一个整数，表示小 Z 最早乘坐旅游巴士离开景区的时刻。如果不存在符合要求的旅游方案，输出 -1。

样例 #1 样例输入 #1 5 5 3 1 2 0 2 5 1 1 3 0 3 4 3 4 5 1 样例输出 #1 6 提示

【样例 #1 解释】

小 Z 可以在 3 3 3 时刻到达景区入口，沿 1 → 3 → 4 → 5 1 \to 3 \to 4 \to 5 1→3→4→5 的顺序走到景区出口，并在 6 6 6 时刻离开。

【样例 #2】

见附件中的 bus/bus2.in 与 bus/bus2.ans。

【数据范围】

对于所有测试数据有： 2 ≤ n ≤ 1 0 4 2 \leq n \leq 10 ^ 4 2≤n≤104， 1 ≤ m ≤ 2 × 1 0 4 1 \leq m \leq 2 \times 10 ^ 4 1≤m≤2×104， 1 ≤ k ≤ 100 1 \leq k \leq 100 1≤k≤100， 1 ≤ u i , v i ≤ n 1 \leq u _ i, v _ i \leq n 1≤ui,vi≤n， 0 ≤ a i ≤ 1 0 6 0 \leq a _ i \leq 10 ^ 6 0≤ai≤106。

测试点编号 n ≤ n \leq n≤ m ≤ m \leq m≤ k ≤ k \leq k≤特殊性质 1 ∼ 2 1 \sim 2 1∼2 10 10 10 15 15 15 100 100 100 a i = 0 a _ i = 0 ai=0 3 ∼ 5 3 \sim 5 3∼5 10 10 10 15 15 15 100 100 100无 6 ∼ 7 6 \sim 7 6∼7 1 0 4 10 ^ 4 104 2 × 1 0 4 2 \times 10 ^ 4 2×104 1 1 1 a i = 0 a _ i = 0 ai=0 8 ∼ 10 8 \sim 10 8∼10 1 0 4 10 ^ 4 104 2 × 1 0 4 2 \times 10 ^ 4 2×104 1 1 1无 11 ∼ 13 11 \sim 13 11∼13 1 0 4 10 ^ 4 104 2 × 1 0 4 2 \times 10 ^ 4 2×104 100 100 100 a i = 0 a _ i = 0 ai=0 14 ∼ 15 14 \sim 15 14∼15 1 0 4 10 ^ 4 104 2 × 1 0 4 2 \times 10 ^ 4 2×104 100 100 100 u i ≤ v i u _ i \leq v _ i ui≤vi 16 ∼ 20 16 \sim 20 16∼20 1 0 4 10 ^ 4 104 2 × 1 0 4 2 \times 10 ^ 4 2×104 100 100 100无

【解析】使用优先队列保存当前到达的景点及到达时间，BFS搜索，直至找到到达终点，且时间是k的倍数。悲催的是只有5分o(╥﹏╥)o。详见代码：

#include using namespace std; int n,m,k; int ans=0; vector to[10005];//目标景点 vector a[10005];//开通时间 struct node{ int d;//目前景点 int t;//目前时间 bool operator node tmp; tmp.d=1; tmp.t=0; pq.push(tmp);//起点入队 while (!pq.empty()){ if (ans!=0){//如果找到答案 break; } tmp=pq.top(); pq.pop(); int from=tmp.d;//出发景点 int tx=tmp.t;//出发时间 if(tx>1100000){//超时退出 break; } if (from==n&&tx%k==0){//如果当前是出口，且时间是k的倍数，找到答案 ans=tx; break; } for (int i=0;i//如果该道路已经开放 next.t=tx+1; }else{//如果该道路没有开放 int cha=a[from][i]-tx;//还差cha时间开放 next.t=tx+1+(cha+k-1)/k*k;//晚到入口（差值除k向上取整倍k） } pq.push(next);//下一景点入队 } } } main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i//如果没有答案 cout return d > rhs.d; } }; int main() { int n, m, kk; scanf("%d%d%d", &n, &m, &kk); while (m--) { int u, v, w; scanf("%d%d%d", &u, &v, &w); G[u].push_back({v, w});//邻接表存边 } memset(d, 0x3f, sizeof d);//初始化最小距离 priority_queue q;//优先队列 q.push({1, 0, d[1][0] = 0});//起点入队 while (q.size()) {//只要队列非空，继续 //取当前最小白点（参考dijkstra） int u = q.top().u, i = q.top().i; q.pop(); if (vis[u][i]) continue;//如果已经标记为蓝点，忽略 vis[u][i] = 1;//标记为蓝点 for (auto [v, w] : G[u]) {//枚举该节点的所有边 //计算出发时间和到达时间模k的余数 int t = d[u][i], j = (i + 1) % kk; //如果路线不通，延时k的整数倍时间，保证刚好通过不浪费时间 if (t t + 1) q.push({v, j, d[v][j] = t + 1}); } } //如果不能到达，输出-1 if (d[n][0] == INF) d[n][0] = -1; printf("%d\n", d[n][0]); return 0; }

【本文地址】

CSP

CSP

今日新闻

推荐新闻