提交时间:2022-08-18 11:11:54

运行 ID: 55471

#include<bits/stdc++.h> #define N 1005 using namespace std; inline int read(){ int x(0),f(1);char ch(getchar()); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48),ch=getchar();} return x*f; } int n,m,L,s,t; struct Edge{ int v,w; Edge(int x,int y):v(x),w(y){} }; struct Node{ int u,d; Node(int x,int y):u(x),d(y){} inline bool operator < (const Node&x) const {return d<x.d;} }; vector <Edge> G[N]; priority_queue <Node> Q; int dis[2][N],f[N][2]; inline void Dij(int op){ Q.push(Node(s,0)); while(!Q.empty()){ int u(Q.top().u);Q.pop(); for(int i(0);i<G[u].size();++i){ if(!op&&!G[u][i].w) continue; int v(G[u][i].v),w(dis[op][u]+G[u][i].w); if(op&&!G[u][i].w) ++w; if(dis[op][v]>w){ if(op){f[v][0]=u;f[v][1]=G[u][i].w;} Q.push(Node(v,dis[op][v]=w)); } } } } int ans[N][N]; int main(){ // freopen("Hotel.in","r",stdin); // freopen("Hotel.out","w",stdout); n=read();m=read();L=read();s=read();t=read(); for(int u(0);u<n;++u) for(int v(0);v<n;++v) ans[u][v]=-1; for(int i(1);i<=m;++i){ int a(read()),b(read()),c(read()); G[a].push_back(Edge(b,c)); G[b].push_back(Edge(a,c)); ans[a][b]=ans[b][a]=c; } memset(dis,0x3f3f3f3f,sizeof(dis)); dis[0][s]=dis[1][s]=0;Dij(0);Dij(1); if(L<dis[1][t]||L>dis[0][t]) puts("NO"); else{ puts("YES"); if(dis[0][t]^dis[1][t]){ for(int now(t);now^s;now=f[now][0]) if(!f[now][1]){ ans[now][f[now][0]]=L-dis[1][t]+1; ans[f[now][0]][now]=L-dis[1][t]+1; } } for(int u(0);u<n;++u) for(int v(0);v<n;++v) if(!ans[u][v]) ans[u][v]=1; for(int u(1);u<n;++u) for(int v(0);v<u;++v) if(~ans[u][v]) printf("%d %d %d\n",u,v,ans[u][v]); } return 0; }