Advertisement
jeff69

Untitled

Sep 17th, 2016
110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.18 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. typedef long long ll;
  3. typedef long double ld;
  4. using namespace std;
  5.  
  6. int n,m,l,s,t;
  7. const int MX=1e3+4;
  8. vector<int> adj[MX];
  9. ll weigh[1005][1005];
  10. vector<pair<int,int> > un;
  11. priority_queue<pair<ll, int> > pq;
  12. bool vis[1002];
  13. ll dijktra()
  14. {
  15. memset(vis,0,sizeof vis);
  16. pq.push({0,s});
  17. while(!pq.empty())
  18. {
  19. int nx=pq.top().second;
  20. if(vis[nx])
  21. {
  22. pq.pop();
  23. continue;
  24. }
  25. vis[nx]=1;
  26. if(nx==t)
  27. {
  28. return -1*pq.top().first;
  29. }
  30. for(int i=0;i<adj[nx].size();i++)
  31. {
  32. int y=adj[nx][i];
  33. pq.push({pq.top().first+ (-1*weigh[y][nx]),y});
  34. }
  35. pq.pop();
  36. }
  37. }
  38. int main()
  39. {
  40. cin>>n>>m>>l>>s>>t;
  41. for(int i=0;i<m;i++)
  42. {
  43. int x,y,z;
  44. scanf("%d%d%d",&x,&y,&z);
  45. adj[x].push_back(y);
  46. adj[y].push_back(x);
  47. if(z==0){
  48. un.push_back({x,y});
  49. if(weigh[x][y]!=0)continue;
  50. weigh[x][y]=1e9+3;
  51. weigh[y][x]=1e9+3;
  52. continue;
  53. }
  54. if(weigh[x][y]<z&&weigh[x][y]!=0)continue;
  55. weigh[x][y]=z;
  56. weigh[y][x]=z;
  57.  
  58. }
  59. if(dijktra()==l)
  60. {
  61. cout<<"YES"<<endl;
  62. for(int c=0;c<1001;c++)
  63. for(int w=c+1;w<1001;w++)
  64. if(weigh[c][w])
  65. cout<<c<<' '<<w<<' '<<weigh[c][w]<<endl;;
  66. return 0;
  67. }
  68. for(int i=0;i<un.size();i++)
  69. {
  70. int a=un[i].first;
  71. int b=un[i].second;
  72. ll en,st,mid;
  73. en=weigh[a][b];
  74. st=1;
  75. while(st<=en)
  76. {
  77. mid=(st+en)/2;
  78. while(!pq.empty())pq.pop();
  79. weigh[a][b]=mid;
  80. weigh[b][a]=mid;
  81.  
  82. ll re =dijktra();
  83. if(re<l)
  84. {
  85. st=mid+1;
  86. }
  87. else if (re>l)
  88. {
  89. en=mid-1;
  90. }
  91. else{
  92. cout<<"YES"<<endl;
  93. for(int c=0;c<1001;c++)
  94. for(int w=c+1;w<1001;w++)
  95. if(weigh[c][w])
  96. cout<<c<<' '<<w<<' '<<weigh[c][w]<<endl;;
  97. return 0;
  98. }
  99. }
  100.  
  101. }
  102. cout<<"NO";
  103. return 0;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement