提交时间:2022-08-18 10:59:47

运行 ID: 55426

#include<bits/stdc++.h> using namespace std; template<typename T>void in(T &a) { T ans=0; bool f=0; char c=getchar(); for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1; for(;c>='0'&&c<='9';c=getchar())ans=ans*10+c-'0'; a=(f?-ans:ans); } void dijkstra(int st,int n,vector<pair<int,long long> >e[],long long dis[],int path[]){ bool vis[n+5]; priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > >q; for(int i=1;i<=n;i++)dis[i]=0x3f3f3f3f3f3f3f3f,path[i]=-1; memset(vis,0,sizeof(vis)),q.push(make_pair(0,st)),dis[st]=0; while(!q.empty()){ int now=q.top().second; q.pop(); if(vis[now])continue; vis[now]=1; for(int i=0;i<e[now].size();i++){ int v=e[now][i].first; long long w=e[now][i].second; if((dis[now]+w)<dis[v])dis[v]=dis[now]+w,path[v]=now,q.push(make_pair(dis[v],v)); } } } int get_path(int st,int to,int path[],int path1[],int cnt=1){ path1[1]=st; stack<int>temp; while(path[to]!=-1)temp.push(to),to=path[to]; while(!temp.empty())path1[++cnt]=temp.top(),temp.pop(); return cnt; } int n,m,l,s,t,cnt,temp[1005],path[1005]; long long dis[1005],a[1005][1005]; vector<pair<int,long long> >e[1005]; bool f,b[1005][1005]; int main(){ memset(a,-1,sizeof(a)),in(n),in(m),in(l),in(s),in(t),s++,t++; for(int i=1,u,v,w;i<=m;i++)in(u),in(v),in(w),u++,v++,e[u].push_back(make_pair(v,w)),e[v].push_back(make_pair(u,w)),a[u][v]=a[v][u]=w; dijkstra(s,n,e,dis,temp),cnt=get_path(s,t,temp,path); if(dis[t]>l)return puts("NO"),0; for(int i=2;i<=cnt;i++){ if(a[path[i-1]][path[i]]==0){ if(!f)a[path[i-1]][path[i]]+=(l-dis[t]),a[path[i]][path[i-1]]+=(l-dis[t]),f=1; b[path[i-1]][path[i]]=b[path[i]][path[i-1]]=1; } } if(!f&&dis[t]!=l)return puts("NO"),0; for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(a[i][j]!=-1)printf("%d %d %d\n",i-1,j-1,(a[i][j]==0&&!b[i][j])?1000000000:a[i][j]); return 0; }