4473: 旅游巴士 [CSP-J 2023]

#include<bits/stdc++.h>
using namespace std;
//解法1：暴力解法，枚举起始时间+BFS求单源最短路-时间复杂度-O(nq)
const int N = 1e4+10;
int n,m,k;
vector<pair<int,int> > g[N]; //邻接表
bool vis[N]; //标记数组
struct point {
	int v,t;
}; 
int ans=0x3f3f3f3f; //记录最早离开时间 

//bfs求单源最短路
void bfs(point s) {
	queue<point> q;
	q.push(s);vis[s.v] = 1;
	while (!q.empty()) {
		point u=q.front();q.pop();
		if (u.v==n && u.t%k==0) {
			ans=min(ans,u.t);
			return ;
		}
		for(int i=0;i<g[u.v].size();i++) {
			int v=g[u.v][i].first,a=g[u.v][i].second;
			if(u.t>=a && !vis[v]) {
				q.push({v,u.t+1});
				if(v!=n) vis[v]=1;
			}
		}
	}
} 
int main(){
    cin>>n>>m>>k;
    int maxa=0,f=1;
    for(int i=1;i<=m;i++) {
    	int u,v,a;cin>>u>>v>>a;
    	g[ u ].push_back({v,a }); //邻接表存图
		maxa=max(maxa,a);
		if(a!=0) f=0; 
    	
	}
	//特判：当k=1并且f=1本题变成单源最短路问题
	if(k==1&&f==1) bfs({1,0});
	else {
		//枚举起点+单源最短路
		for(int t=0;t<=maxa;t+=k) {
			memset(vis,0,sizeof(vis));
			bfs({1,t});
		} 
	}
	cout<<ans<<endl; 
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
//解法2：每个点到达时间按照对k取余进行分类构建k层分层图，使用堆优化dijkstra跑分层图的最短路，时间复杂度-O（nk*log(nk)）
const int N = 1e6 + 10;
vector<pair<int, int>> g[N];//邻接表
int min_dis [N];//最短路数组-最短到达时间
int main() {
  int n, m, k;  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    int u, v, a;  cin >> u >> v >> a;
    for (int j = 0; j < k; j++) {
      //构建k层分层图，每个点到达时间按照对k取余进行分类
      g[j * n + u].push_back({ (j + 1) % k * n + v,a });
    }
  }
  //初始化最短路数组 
  for (int i = 1; i <= n * k; i++) min_dis[i] = 1e9;

  //用堆优化dijkstra跑分层图求最短路
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  min_dis[1] = 0;   pq.push({ 0,1 });

  while (!pq.empty()) {
    int t = pq.top().first, cur = pq.top().second;  pq.pop();
    if (t <= min_dis[cur]) {
      for (auto e : g[cur]) {
        int tmp = min_dis[cur] + 1;
        //如果到达当前节点的时刻小于当前节点的开放时间，则重置使满足条件的最早到达时间
        if (min_dis[cur] < e.second) tmp += ceil((e.second - min_dis[cur]) * 1.0 / k) * k;
        //更新最短路数组
        if (tmp < min_dis[e.first]) {
          min_dis[e.first] = tmp;
          pq.push({ min_dis[e.first],e.first });
        }
      }
    }
  }
  if (min_dis[n] == 1e9) cout << "-1" << endl;
  else cout << min_dis[n] << endl;
  return 0;
}