无17831513
2025-07-28 10:38:10
发布于：江苏
6阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
const int N=1e4;
int n,m,k;
struct node{
int v,a;
};
vector<node>g[N+5];
bool vis[N+5];
int dist[N+5];
struct Q{
int id,time;
};
struct cmp{
bool operator()(Q a,Q b){
return a.time>b.time;
}
};
void dj(int s){
memset(dist,0x3f,sizeof dist);
priority_queue<Q,vector<Q>,cmp> q;//优先队列
q.push({s,0});
dist[s]=0;
while(q.size()){
Q f=q.top();q.pop();
int u = f.id;
vis[u]=1;
for(int i=0;i<g[u].size();++i){
int v =g[u][i].v;
int a =g[u][i].a;
if(vis[v]) continue;
if(dist[u] >= a){
if(dist[u]+1<dist[v]){
dist[v]=dist[u]+1;
q.push({v,dist[v]});
}
}
else{
if(a+1<dist[v]){
dist[v]=a+1;
q.push({v,dist[v]});
}
}
}
}
}
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;
g[u].push_back((node){v,a});
}
dj(1);
if(dist[n]==0x3f3f3f3)cout<<-1;
else cout<<dist[n];
fclose(stdin);
fclose(stdout);
return 0;
}
这里空空如也
有帮助，赞一个