P9751 [CSP-J 2023] 旅游巴士

• $P9751$

• 部分分思路

题目要求时间必须是 $k$ 的非负整数倍，所以想到了升维。这样就变成了一道分层图最短路的题目。用 BFS 算法可以拿到 $A_i=0$ 的 $35$ 分。

• 满分思路

其实部分分的思路已经很接近正解了，想要拿到满分只需要做一点小小的调整。虽然说不能在路上停留，但是我们可以晚一点到达起点。但是要注意：到达起点的时间也必须是 $k$ 的倍数。这个做法 BFS 就解决不了了（它只能解决出发时间相同且边权为 $1$ 的最短路问题），我们可以使用 Dijkstra 算法来解决这道题。时间复杂度约 $O($ $n$ $+$ $m\cdot lo{g}_{2}m$ $)$。

• 代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f3f; // 极大值∞int n, m, k;
int dis[10010][110]; // 最短路
int vis[10010][110]; // 记录点有没有被选过struct edge // 边
{int y, w;
} ;struct node // 优先队列中的点
{int x, t, d;bool operator < (const node b) const // 重载运算符{return d > b.d;}
} ;vector<edge> g[10010]; // 图void add(int x, int y, int w) // 建边
{g[x].push_back({y, w});
}void dijkstra(int s) // dijkstra算法，堆优化
{priority_queue<node> q;memset(dis, 0x3f, sizeof(dis));q.push({s, 0, 0});dis[s][0] = 0;while (q.size()){int x = q.top().x;int t = q.top().t;q.pop();if (vis[x][t])continue;vis[x][t] = 1;int nt = (t + 1) % k;for (int i = 0; i < g[x].size(); i++){int y = g[x][i].y;int w = g[x][i].w;int d = dis[x][t];if (d < w) d += (w - d + k - 1) / k * k; // 到达起点时间if (dis[y][nt] > d + 1){dis[y][nt] = d + 1;q.push({y, nt, dis[y][nt]});}}}
}int main()
{cin >> n >> m >> k;for (int i = 1; i <= m; i++){int u, v, w;cin >> u >> v >> w;add(u, v, w); // 建条单向边}dijkstra(1);if (dis[n][0] == INF)cout << "-1" << endl; // 无解else cout << dis[n][0] << endl;return 0;
}