fork(1) download
copy 
  1. 	#include <bits/stdc++.h>
  2. 	using namespace std;
  3. 	#define lli long long int
  4. 	#define lld long double
  5. 	#define nodecnt 100005
  6. 	#define INF (1<<20)
  7. 	#define mod 1000000007
  8. 	lld key[nodecnt],x[nodecnt],y[nodecnt];
  9. 	bool donewith[nodecnt];
  10. 	lli nodes,edges,start,dest,p,ans;
  11. 	std::vector<pair<lli,lli> > graph[nodecnt] ;
  12. 	lld eucdist(lli i,lli j)
  13. 	{
  14. 		return ceil(p*sqrt(((x[i]-x[j])*(x[i]-x[j]))+((y[i]-y[j])*(y[i]-y[j]))));
  15. 	}
  16. 	void prims()
  17. 	{
  18. 		ans=0;
  19. 		set<pair<lld,lli> > Q;
  20. 		for(lli i=1;i<=nodes;i++)
  21. 			key[i]=INF,donewith[i]=false,Q.insert(make_pair(key[i],i));
  22.  
  23. 		Q.erase(Q.find(make_pair(key[start],start)));
  24. 		key[start]=0;
  25.  
  26. 		Q.insert(make_pair(key[start],start));
  27. 		while(!Q.empty())
  28. 		{
  29. 			pair<lld,lli> top=*(Q.begin());
  30. 			Q.erase(Q.begin());
  31. 			lli u=top.second;
  32. 			donewith[u]=true;
  33. 			if(u!=start)
  34. 			{
  35. 				ans+=top.first;
  36. 				if(ans>=mod)
  37. 					ans=ans%mod;
  38. 			}		
  39. 			lli size=graph[u].size();
  40. 			for(lli i=0;i<size;i++)
  41. 			{
  42. 				lli v=graph[u][i].first;
  43. 				lld w=graph[u][i].second;
  44. 				if(donewith[v]==false)
  45. 				{	
  46. 					if(key[v]>w)
  47. 					{
  48. 						Q.erase(Q.find(make_pair(key[v],v)));
  49. 						key[v]=w;
  50. 						Q.insert(make_pair(key[v],v));
  51. 					}
  52. 				}
  53. 			}
  54. 		}
  55. 	}
  56. 	int main(int argc, char const *argv[])
  57. 	{
  58. 		lli t;
  59. 		scanf("%lld",&t);
  60. 		for(lli T=1;T<=t;T++)
  61. 		{
  62. 			scanf("%lld %lld",&nodes,&p);
  63. 			for(lli i=1;i<=nodes;i++)
  64. 				graph[i].clear();
  65. 			for(lli i=1;i<=nodes;i++)
  66. 				scanf("%Lf %Lf",&x[i],&y[i]);
  67. 			for(lli i=1;i<=nodes;i++)
  68. 			{
  69. 				for(lli j=i+1;j<=nodes;j++)
  70. 				{
  71. 					lld temp=eucdist(i,j);
  72. 					graph[i].push_back(make_pair(j,temp));
  73. 					graph[j].push_back(make_pair(i,temp));
  74. 				}
  75. 			}
  76. 			start=1,ans=0;
  77. 			prims();
  78. 			printf("Scenario #%lld: %lld\n",T,ans);
  79. 		}
  80. 		return 0;
  81. 	}
Success #stdin #stdout 0s 8064KB
comments (?)
stdin
copy 
2

4 1

35 46

29 13

44 0

27 17

3 18

18 0

11 17

2 31
stdout
copy 
Scenario #1: 56
Scenario #2: 631
https://ideone.com/7nYL0W
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!