fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb(a) push_back(a)
  4. #define mp(a,b) make_pair(a,b)
  5. //#define f first
  6. //#define s second
  7. #define ll long long
  8. #define mod 1000000007
  9. #define N 1009
  10. typedef map<pair<int,int>,ll> Mapp;
  11. ll n,m,a,b,c,d,k,h,w,x,y,p,q,s,L,t,ans,res,ma,mi,T,act=0,pas=1,inf=1e18;
  12. struct node
  13. {
  14. 	int x,w;
  15. 	node(){}
  16. 	node(int a,int b)
  17. 	{
  18. 		x=a;w=b;
  19. 	}
  20. };
  21. vector<node> v[N];
  22. vector<int> pre(N,0);
  23. Mapp edges;
  24. int zeroes[N];//min zeroes on path from s to i
  25. struct node2
  26. {
  27. 	int x,p;
  28. 	ll w;
  29. 	node2(){}
  30. 	node2(int a,ll c,int b)
  31. 	{
  32. 		x=a;p=b;
  33. 		w=c;
  34. 	}
  35. };
  36. struct cmp{
  37. bool operator()(node2 a,node2 b)
  38. {
  39. 	return a.w>b.w;
  40. }};
  41. ll dijkstra()//fills pre
  42. {
  43. 	priority_queue<node2,vector<node2>,cmp> p;
  44. 	ll h[N]={0};
  45. 	node2 a=node2(s,0,-1);
  46. 	p.push(a);
  47. 	while(!p.empty())// not in same component
  48. 	{
  49. 		a=p.top();
  50. 		p.pop();
  51. 		if(!h[a.x])
  52. 		{
  53. 			pre[a.x]=a.p;
  54. 			h[a.x]=a.w;
  55. 			if(a.x==t){/*cout<<a.x<<" "<<t<<endl;*/return a.w;}
  56. 			for(int i=0;i<v[a.x].size();i++)
  57. 			{
  58. 				int u=v[a.x][i].x;
  59. 				if(u==a.x)continue;
  60. 				if(h[u]==0)p.push(node2(u,a.w+v[a.x][i].w,a.x));
  61. 			}
  62. 		}
  63. 	}
  64. 	//cout<<"here"<<endl;
  65. 	return L+1;
  66. }
  67. ll assign(int id,int z,ll len)
  68. {
  69. 	if(pre[id]==-1)return len;
  70. 	int c=edges[mp(min(id,pre[id]),max(id,pre[id]))];
  71. 	//cout<<"id="<<id<<" pre[id]="<<pre[id]<<" c="<<c<<" len="<<len<<endl;
  72. 	if(c==0)
  73. 	{
  74. 		if(T==0)return inf;
  75. 		T--;
  76. 		edges[mp(min(id,pre[id]),max(id,pre[id]))]=1;
  77. 		ll total=assign(pre[id],z+1,len+1);
  78. 		if(total<T)
  79. 		{
  80. 			edges[mp(min(id,pre[id]),max(id,pre[id]))]+=T-total;
  81. 			T=0;
  82. 		}
  83. 		//cout<<"id="<<id<<" total="<<total<<endl;
  84. 		return max(L,total);
  85. 	}
  86. 	else
  87. 	{
  88. 		//T-=c;
  89. 		ll total=assign(pre[id],z,len+c);
  90. 		//cout<<"id="<<id<<" total="<<total<<endl;
  91. 		return total;
  92. 	}
  93. }
  94. int main() 
  95. {
  96. 	ios_base::sync_with_stdio(false);cin.tie(NULL);
  97. 	cin>>n>>m>>L>>s>>t;
  98. 	s++;t++;
  99. 	T=L;
  100. 	for(int i=0;i<m;i++)
  101. 	{
  102. 		cin>>a>>b>>c;
  103. 		a++;b++;
  104. 		v[a].pb(node(b,c));
  105. 		v[b].pb(node(a,c));
  106. 		edges[mp(min(a,b),max(a,b))]=c;
  107. 	}
  108. 	d=dijkstra();// fills pre
  109. 	//cout<<d<<endl;
  110. 	if(d>L){cout<<"NO";return 0;}
  111. 	//backtrack();//fills zeroes[] using pre[]
  112. 	//for(int i=0;i<=6;i++)cout<<pre[i]<<" ";cout<<endl;
  113. 	d=assign(t,0,0);//using zeroes, reassigns edges.
  114. 	//cout<<d<<endl;
  115. 	if(d!=L){cout<<"NO";return 0;}
  116. 	cout<<"YES"<<endl;
  117. 	for(Mapp::iterator it=edges.begin();it!=edges.end();it++)
  118. 	{
  119. 		cout<<it->first.first-1<<" "<<it->first.second-1<<" ";
  120. 		if(it->second==0)cout<<inf;
  121. 		else cout<<it->second;
  122. 		cout<<endl;
  123. 	}
  124. 	return 0;
  125. }
Success #stdin #stdout 0s 3488KB
comments (?)
stdin
copy 
2 1 999999999 1 0
0 1 1000000000
stdout
copy 
NO
https://ideone.com/m3Kjuu
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!