fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define vi vector<int>
  4. #define vl vector<ll>
  5. #define pl pair<ll,ll>
  6. #define pi pair<int,int>
  7. #define all(v) v.begin(),v.end()
  8. #define pb push_back
  9. #define task "tunnel"
  10. #define TIME (1.0*clock()/CLOCKS_PER_SEC)
  11. using namespace std;
  12. int n,m;
  13. int a,b,c,d;
  14. ll da[500505];
  15. ll db[500505];
  16. ll dc[500505];
  17. ll dd[500505];
  18. vector<pi> adj[500505];
  19. vi dag[500505];
  20. vi rev[500505];
  21. struct edges{
  22. 	int fi,se,wei;
  23. } e[500505];
  24. void dijk(int u,ll d[])
  25. {
  26. 	priority_queue<pl,vector<pl>,greater<pl>>pq;
  27. 	pq.push({0,u});
  28. 	for(int i=1;i<=n;i++)
  29. 	{
  30. 		d[i]=1e18;
  31. 	}
  32. 	d[u]=0;
  33. 	while(!pq.empty())
  34. 	{
  35. 		ll dist=pq.top().first;
  36. 		int v=pq.top().second;
  37. 		pq.pop();
  38. 		if(dist>d[v])continue;
  39. 		for(auto &k:adj[v])
  40. 		{
  41. 			int x=k.first;
  42. 			ll w=k.second;
  43. 			if(d[x]>d[v]+w)d[x]=d[v]+w,pq.push({d[x],x});
  44. 		}
  45. 	}
  46. }
  47. bool chosenone[500505];
  48. int deg[500505];
  49. int rdeg[500505];
  50. ll fc[500505];
  51. ll fd[500505];
  52. void sol()
  53. {
  54. 	cin>>n>>m;
  55. 	cin>>a>>b>>c>>d;
  56. 	for(int i=1;i<=m;i++){
  57. 		int u,v,w;
  58. 		cin>>u>>v>>w;
  59. 		e[i]={u,v,w};
  60. 		adj[u].pb({v,w});
  61. 		adj[v].pb({u,w});
  62. 	}    
  63. 	dijk(a,da);
  64. 	dijk(b,db);
  65. 	dijk(c,dc);
  66. 	dijk(d,dd);
  67. 	for(int i=1;i<=m;i++)
  68. 	{
  69. 		int u=e[i].fi;
  70. 		int v=e[i].se;
  71. 		int w=e[i].wei;
  72. 		if(da[u]+w==da[v]
  73. && da[u]+w+db[v]==da[b])
  74. 		{
  75. 			dag[u].pb(v);
  76. 			rev[v].pb(u);
  77. 			deg[v]++;
  78. 			rdeg[u]++;
  79. 			chosenone[u]=1;
  80. 			chosenone[v]=1;
  81. 		}
  82. 		if(da[v]+w==da[u]
  83. && da[v]+w+db[u]==da[b])
  84. 		{
  85. 			dag[v].pb(u);
  86. 			rev[u].pb(v);
  87. 			deg[u]++;
  88. 			rdeg[v]++;
  89. 			chosenone[u]=1;
  90. 			chosenone[v]=1;
  91. 		}
  92. 	}
  93.  
  94. 	queue<int>q,q2;
  95. 	ll ans=dc[d];
  96. 	for(int i=1;i<=n;i++)
  97. 	{
  98. 		fc[i]=dc[i];
  99. 		fd[i]=dd[i];
  100.  
  101. 		if(chosenone[i]){
  102. 			// cout<<fc[i]<<" "<<fd[i]<<" "<<i<<"\n";
  103. 		}
  104. 	}
  105. 	q.push(a);q2.push(b);
  106.  
  107. 	while(!q.empty())
  108. 	{
  109. 		int t=q.front();
  110. 		q.pop();ans=min(fc[t]+dd[t],ans);
  111. 		cout<<fc[t]<<" "<<dd[t]<<" "<<t<<" "<<ans<<"\n";
  112. 		for(auto &x:dag[t])
  113. 		{
  114. 			fc[x]=min(fc[x],fc[t]);
  115.  
  116. 			if(--deg[x]==0)q.push(x);		
  117. 		}
  118.  
  119. 	}
  120. 	while(!q2.empty())
  121. 	{
  122. 		int t=q2.front();
  123. 		q2.pop();ans=min(fd[t]+dc[t],ans);
  124.  
  125.  
  126. 		for(auto &x:rev[t])
  127. 		{
  128. 			fd[x]=min(fd[x],fd[t]);
  129.  
  130. 			if(--rdeg[x]==0)q2.push(x);
  131. 		}
  132.  
  133. 	}
  134. 	cerr<<ans<<"\n";
  135.  
  136. }
  137. int main()
  138. {
  139.     ios_base::sync_with_stdio(0);
  140.     cin.tie(0);
  141.     if(fopen(task".inp","r"))
  142.     {
  143.         freopen(task ".inp","r",stdin);
  144.         freopen(task ".out","w",stdout);
  145.     }
  146.     sol();
  147.     cerr<<"Time : "<<TIME<<"s"<<"\n";
  148.     return 0;
  149. }
Success #stdin #stdout #stderr 0.02s 48900KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0 0 0
stderr
copy 
0
Time : 0.012343s
https://ideone.com/ymbkFM
language:
C++14 (gcc 8.3)
created:
3 days 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!