提交时间:2022-08-18 11:00:04

运行 ID: 55427

#include <bits/stdc++.h> using namespace std; const int N =1e6+10; long long vis[N],dis[N],u[N],v[N],w[N]; struct node { int v,w; }; vector<node> g[N<<1]; vector<int> G; int n,m,L,s,t; void dijkstra(int s) { for(int i=0; i<=n; i++) dis[i]=INT_MAX,vis[i]=0; priority_queue< pair<int,int> > q; q.push(make_pair(0,s)); dis[s]=0; while(q.size()) { int x=q.top().second; q.pop(); if(vis[x]) continue; vis[x]=1; for(int i=0; i<g[x].size(); i++) { int y=g[x][i].v; if(dis[x]+g[x][i].w<dis[y]) { dis[y]=dis[x]+g[x][i].w; q.push(make_pair(-dis[y],y)); } } } } void out(int now) { cout<<"YES"<<endl; for(int j=1; j<=m; j++) { if(w[j]==0) { if(j<now) cout<<u[j]<<" "<<v[j]<<" "<<1<<endl; if(j==now) cout<<u[j]<<" "<<v[j]<<" "<<L-dis[t]+1<<endl; if(j>now) cout<<u[j]<<" "<<v[j]<<" "<<INT_MAX<<endl; } else cout<<u[j]<<" "<<v[j]<<" "<<w[j]<<endl; } } int main() { cin>>n>>m>>L>>s>>t; for(int i=1; i<=m; i++) { cin>>u[i]>>v[i]>>w[i]; if(w[i]==0) { G.push_back(i); continue; } g[u[i]].push_back({v[i],w[i]}); g[v[i]].push_back({u[i],w[i]}); } dijkstra(s); if(dis[t]<L) cout<<"NO",exit(0); else if(dis[t]==L) { cout<<"YES"<<endl; for(int i=1; i<=m; i++) { if(!w[i]) cout<<u[i]<<" "<<v[i]<<" "<<INT_MAX<<endl; else cout<<u[i]<<" "<<v[i]<<" "<<w[i]<<endl; } exit(0); } else if(dis[t]>L) { for(int i=0; i<G.size(); i++) { g[u[G[i]]].push_back({v[G[i]],1}); g[v[G[i]]].push_back({u[G[i]],1}); dijkstra(s); if(dis[t]>L) continue; if(dis[t]<=L) { int now=G[i]; out(now); exit(0); } } } cout<<"NO"<<endl; return 0; }