Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
119003 | 陈家宝 | T2 酒店 | C++ | 通过 | 100 | 40 MS | 47140 KB | 1885 | 2024-01-03 13:15:40 |
#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"; return 0; }