Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- typedef long long ll;
- typedef long double ld;
- using namespace std;
- int n,m,l,s,t;
- const int MX=1e3+4;
- vector<int> adj[MX];
- ll weigh[1005][1005];
- vector<pair<int,int> > un;
- priority_queue<pair<ll, int> > pq;
- bool vis[1002];
- ll dijktra()
- {
- memset(vis,0,sizeof vis);
- pq.push({0,s});
- while(!pq.empty())
- {
- int nx=pq.top().second;
- if(vis[nx])
- {
- pq.pop();
- continue;
- }
- vis[nx]=1;
- if(nx==t)
- {
- return -1*pq.top().first;
- }
- for(int i=0;i<adj[nx].size();i++)
- {
- int y=adj[nx][i];
- pq.push({pq.top().first+ (-1*weigh[y][nx]),y});
- }
- pq.pop();
- }
- }
- int main()
- {
- cin>>n>>m>>l>>s>>t;
- for(int i=0;i<m;i++)
- {
- int x,y,z;
- scanf("%d%d%d",&x,&y,&z);
- adj[x].push_back(y);
- adj[y].push_back(x);
- if(z==0){
- un.push_back({x,y});
- if(weigh[x][y]!=0)continue;
- weigh[x][y]=1e9+3;
- weigh[y][x]=1e9+3;
- continue;
- }
- if(weigh[x][y]<z&&weigh[x][y]!=0)continue;
- weigh[x][y]=z;
- weigh[y][x]=z;
- }
- if(dijktra()==l)
- {
- cout<<"YES"<<endl;
- for(int c=0;c<1001;c++)
- for(int w=c+1;w<1001;w++)
- if(weigh[c][w])
- cout<<c<<' '<<w<<' '<<weigh[c][w]<<endl;;
- return 0;
- }
- for(int i=0;i<un.size();i++)
- {
- int a=un[i].first;
- int b=un[i].second;
- ll en,st,mid;
- en=weigh[a][b];
- st=1;
- while(st<=en)
- {
- mid=(st+en)/2;
- while(!pq.empty())pq.pop();
- weigh[a][b]=mid;
- weigh[b][a]=mid;
- ll re =dijktra();
- if(re<l)
- {
- st=mid+1;
- }
- else if (re>l)
- {
- en=mid-1;
- }
- else{
- cout<<"YES"<<endl;
- for(int c=0;c<1001;c++)
- for(int w=c+1;w<1001;w++)
- if(weigh[c][w])
- cout<<c<<' '<<w<<' '<<weigh[c][w]<<endl;;
- return 0;
- }
- }
- }
- cout<<"NO";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement