旅游巴士 题解

经典最短路问题+优先队列
#include<bits/stdc++.h>
#include<vector>
#include<queue>
using namespace std;
const int N=1e4+5;
struct node{
int u,i,d;//按照d的时间从小到大排序
bool operator <(const node &a) const{
return d>a.d;
}
};
int n,m,k,dp[N][105];
bool vis[N][105];
vector<pair<int,int>>ve[N];
int main(){
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int u,v,a;
cin>>u>>v>>a;
ve[u].push_back({v,a});
}
memset(dp,0x3f,sizeof dp);
priority_queue<node>q;
dp[1][0]=0;//更新起点的所到达时间
q.push({1,0,0});//把起点存入队列中
while(q.size()){
int u=q.top().u,i=q.top().i;//取模后的时间
q.pop();
if(vis[u][i])continue;//曾经已经来过最短的了
vis[u][i]=1;
for(auto [v,w]:ve[u]){
int t=dp[u][i],p=(i+1)%k;
if(t<w)t+=(w-t+k-1)/k*k;
if(dp[v][p]>t+1)q.push({v,p,dp[v][p]=t+1});
}
}
cout<<(dp[n][0]==0x3f3f3f3f?-1:dp[n][0]);
fclose(stdin);
fclose(stdout);
return 0;
}