P9751 [CSP-J 2023] 旅游巴士

• $P9751$

• 部分分思路

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

• 满分思路

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

• 代码

#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;
}